login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A253511 Number of n-bit binary strings in which the length of any run of ones is a power of two. 1
1, 2, 4, 7, 14, 26, 49, 93, 176, 333, 630, 1192, 2255, 4267, 8073, 15274, 28900, 54679, 103455, 195741, 370348, 700713, 1325774, 2508412, 4746007, 8979617, 16989761, 32145244, 60819967, 115073582, 217723390, 411940547, 779406450, 1474665262, 2790120139 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

FORMULA

a(n) = a(n-1) + Sum_{k>=0} a(n-(1+2^k)), with a(-1) = a(0) = 1 and a(n) = 0 for n < -1.

G.f.: (1 + h(x))/(1 - x - x*h(x)) where h(x) = sum(k >= 0, x^(2^k)) is the g.f. of A209229. - Robert Israel, Jan 04 2015

EXAMPLE

For n = 4, the a(4) = 14 solutions are 0000, 0001, 0010, 0100, 1000, 0101, 1001, 1010, 0011, 0110, 1100, 1011, 1101, and 1111.

MAPLE

a:= proc(n) option remember; `if`(n<1, 1,

      a(n-1) +add(a(n-1-2^k), k=0..ilog2(n)))

    end:

seq(a(n), n=0..50);  # Alois P. Heinz, Jan 03 2015

MATHEMATICA

terms = 35; h[x_] = Sum[x^2^k, {k, 0, Log[2, terms] // Floor}];

CoefficientList[(1 + h[x])/(1 - x - x h[x]) + O[x]^terms, x] (* Jean-Fran├žois Alcover, Mar 22 2019, after Robert Israel *)

CROSSREFS

Cf. A000079, A023359, A209229.

Sequence in context: A054191 A257792 A079975 * A076739 A017996 A287154

Adjacent sequences:  A253508 A253509 A253510 * A253512 A253513 A253514

KEYWORD

nonn

AUTHOR

Andrew Woods, Jan 02 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 18:38 EDT 2020. Contains 334728 sequences. (Running on oeis4.)