%I #24 Oct 04 2024 06:19:21
%S 1,1,1,1,2,2,1,1,2,2,2,3,4,3,1,1,2,2,2,3,4,3,2,3,4,4,5,7,7,4,1,1,2,2,
%T 2,3,4,3,2,3,4,4,5,7,7,4,2,3,4,4,5,7,7,5,5,7,8,9,12,14,11,5,1,1,2,2,2,
%U 3,4,3,2,3,4,4,5,7,7,4,2,3,4,4,5,7,7,5,5,7,8,9,12,14,11,5,2,3,4,4,5,7,7,5,5
%N G.f.: Product_{k>=1} (1 + x^(2^k-1) + x^(2^k)).
%H N. J. A. Sloane, <a href="/A151552/b151552.txt">Table of n, a(n) for n = 0..16383</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>.
%F a(n) = 1 for 0 <= n <= 3; thereafter write n = 2^i + j, with 0 <= j < 2^i, then a(n) = a(j) + a(j+1), except that a(2^(i+1)-2) = a(2^(i+1)-1) = 1.
%F a(n) = Sum_{k>=0, n+k even} binomial(A000120(n+k),k); the sum may be restricted further to k <= A000523(n+1). - _Hagen von Eitzen_, May 20 2009 [corrected by _Amiram Eldar_, Jul 29 2023]
%e Written as a triangle:
%e 1;
%e 1;
%e 1,1;
%e 2,2,1,1;
%e 2,2,2,3,4,3,1,1;
%e 2,2,2,3,4,3,2,3,4,4,5,7,7,4,1,1;
%e 2,2,2,3,4,3,2,3,4,4,5,7,7,4,2,3,4,4,5,7,7,5,5,7,8,9,12,14,11,5,1,1;
%e 2,2,2,3,4,3,2,3,4,4,5,7,7,4,2,3,4,4,5,7,7,5,5,7,8,9,12,14,11,5,2,3,4,4,5,7,7,5,5,...
%e The rows converge to A151714.
%p G := mul( 1 + x^(2^n-1) + x^(2^n), n=1..20);
%p wt := proc(n) local w,m,i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end:
%p f:=proc(n) local t1,k; global wt; t1:=0; for k from 0 to 20 do if n+k mod 2 = 0 then t1:=t1+binomial(wt(n+k),k); fi; od; t1; end;
%t a[n_] := Sum[If[EvenQ[n + k], Binomial[DigitCount[n + k, 2, 1], k], 0], {k, 0, Floor[Log2[n + 1]]}]; Array[a, 100, 0] (* _Amiram Eldar_, Jul 29 2023 *)
%Y For generating functions of the form Product_{k>=c} (1 + a*x^(2^k-1) + b*x^2^k) for the following values of (a,b,c) see: (1,1,0) A160573, (1,1,1) A151552, (1,1,2) A151692, (2,1,0) A151685, (2,1,1) A151691, (1,2,0) A151688 and A152980, (1,2,1) A151550, (2,2,0) A151693, (2,2,1) A151694.
%Y Cf. A139250, A151550, A151551, A160573, A151702, A151714, A151553.
%K nonn,look
%O 0,5
%A _N. J. A. Sloane_, May 19 2009, Dec 26 2009