%I #30 Oct 04 2024 06:18:29
%S 1,1,2,1,3,4,4,1,3,4,5,5,10,12,8,1,3,4,5,5,10,12,9,5,10,13,15,20,32,
%T 32,16,1,3,4,5,5,10,12,9,5,10,13,15,20,32,32,17,5,10,13,15,20,32,33,
%U 23,20,33,41,50,72,96,80,32,1,3,4,5,5,10,12,9,5,10,13,15,20,32,32,17,5,10,13
%N Expansion of g.f. Product_{n >= 1} (1 + x^(2^n-1) + 2*x^(2^n)).
%C When convolved with [1, 2, 2, 2, ...] gives the toothpick sequence A153006: (1, 3, 6, 9, ...). - _Gary W. Adamson_, May 25 2009
%C This sequence and the Adamson's comment both are mentioned in the Applegate-Pol-Sloane article, see chapter 8 "generating functions". - _Omar E. Pol_, Sep 20 2011
%D D. Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191
%H N. J. A. Sloane, <a href="/A151550/b151550.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.], which is also available at <a href="http://arxiv.org/abs/1004.3036">arXiv:1004.3036v2</a>, [math.CO], 2010.
%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 To get a nice recurrence, change the offset to 0 and multiply the g.f. by x as in the triangle in the example lines. Then we have: a(0)=0; a(2^i)=1; a(2^i-1)=2^(i-1) for i >= 1; otherwise write n = 2^i+j with 1 <= j <= 2^i-2, then a(n) = a(2^i+j) = 2*a(j) + a(j+1).
%e From _Omar E. Pol_, Jun 09 2009, edited by _N. J. A. Sloane_, Jun 17 2009:
%e May be written as a triangle:
%e 0;
%e 1;
%e 1,2;
%e 1,3,4,4;
%e 1,3,4,5,5,10,12,8;
%e 1,3,4,5,5,10,12,9,5,10,13,15,20,32,32,16;
%e 1,3,4,5,5,10,12,9,5,10,13,15,20,32,32,17,5,10,13,15,20,32,33,23,20,33,41,...
%e The rows of the triangle converge to A151555.
%t terms = 100;
%t CoefficientList[Product[(1+x^(2^n-1) + 2 x^(2^n)), {n, 1, Log[2, terms] // Ceiling}] + O[x]^terms, x] (* _Jean-François Alcover_, Aug 05 2018 *)
%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, A151551, A151552, A151553, A151554, A151555, A152980, A153006, A151688.
%Y Cf. A000079. - _Omar E. Pol_, Jun 09 2009
%K nonn
%O 0,3
%A _N. J. A. Sloane_, May 19 2009, Jun 17 2009