A253511 Number of n-bit binary strings in which the length of any run of ones is a power of two.

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

Offset: 0

Author

Andrew Woods, Jan 02 2015

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A000079, A023359, A209229.

Programs

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 *)

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