A160573 G.f.: Product_{k >= 0} (1 + x^(2^k-1) + x^(2^k)).

2, 3, 3, 3, 5, 6, 4, 3, 5, 6, 6, 8, 11, 10, 5, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 6, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 8, 8, 11, 12, 14, 19, 21, 17, 15, 19, 23, 26, 33, 40, 36, 21, 7, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 8, 8

Offset: 0

Author

Hagen von Eitzen, May 20 2009

Keywords

• nonn

Comments

Sequence mentioned in the Applegate-Pol-Sloane article; see Section 9, "explicit formulas." - Omar E. Pol, Sep 20 2011

Examples

			a(5) = binomial(2,0) + binomial(2,1) + binomial(3,2) + binomial(1,3) + binomial(2,4) + binomial(2,5) + ... = 1 + 2 + 3 + 0 + 0 + 0 + ... = 6
From _Omar E. Pol_, Jun 09 2009: (Start)
Triangle begins:
2;
3;3;
3,5,6,4;
3,5,6,6,8,11,10,5;
3,5,6,6,8,11,10,7,8,11,12,14,19,21,15,6;
3,5,6,6,8,11,10,7,8,11,12,14,19,21,15,8,8,11,12,14,19,21,17,15,19,23,26,...
(End)
		

References

• 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

Links

• David 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. [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 arXiv:1004.3036v2
• N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Crossrefs

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.

Row sums of A151683. See A151687 for another version.

Cf. A151552 (g.f. has one factor fewer).

Limiting form of rows of A118977 when that sequence is written as a triangle and the initial 1 is omitted. - N. J. A. Sloane, Jun 01 2009

Cf. A139250, A139251. - Omar E. Pol, Sep 20 2011

Programs

Maple

See A118977 for Maple code.

Mathematica

max = 80; Product[1 + x^(2^k - 1) + x^(2^k), {k, 0, Ceiling[Log[2, max]]}] + O[x]^max // CoefficientList[#, x]& (* Jean-François Alcover, Nov 10 2016 *)

Formula

a(n) = Sum_{i >= 0} binomial(A000120(n+i),i).

For k >= 1, a(2^k-2) = k+1 and a(2^k-1) = 3; otherwise if n = 2^i + j, 0 <= j <= 2^i-3, a(n) = a(j) + a(j+1).

a(n) = 2*A151552(n) + A151552(n-1).