cp's OEIS Frontend

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

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