|
%I #20 Mar 22 2019 09:27:37
%S 1,2,4,7,14,26,49,93,176,333,630,1192,2255,4267,8073,15274,28900,
%T 54679,103455,195741,370348,700713,1325774,2508412,4746007,8979617,
%U 16989761,32145244,60819967,115073582,217723390,411940547,779406450,1474665262,2790120139
%N Number of n-bit binary strings in which the length of any run of ones is a power of two.
%H Alois P. Heinz, <a href="/A253511/b253511.txt">Table of n, a(n) for n = 0..1000</a>
%F 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.
%F 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
%e For n = 4, the a(4) = 14 solutions are 0000, 0001, 0010, 0100, 1000, 0101, 1001, 1010, 0011, 0110, 1100, 1011, 1101, and 1111.
%p a:= proc(n) option remember; `if`(n<1, 1,
%p a(n-1) +add(a(n-1-2^k), k=0..ilog2(n)))
%p end:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jan 03 2015
%t terms = 35; h[x_] = Sum[x^2^k, {k, 0, Log[2, terms] // Floor}];
%t CoefficientList[(1 + h[x])/(1 - x - x h[x]) + O[x]^terms, x] (* _Jean-François Alcover_, Mar 22 2019, after _Robert Israel_ *)
%Y Cf. A000079, A023359, A209229.
%K nonn
%O 0,2
%A _Andrew Woods_, Jan 02 2015
|
