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,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: A347761 A257792 A079975 * A076739 A017996 A287154

Adjacent sequences: A253508 A253509 A253510 * A253512 A253513 A253514

Keyword

nonn

Author

Andrew Woods, Jan 02 2015

Status

approved