1,2

Number of toothpicks added to the toothpick sieve at the n-th step (see A139250).

Note that it appears that if n is equal to 1 plus a power of 2 with positive exponent then a(n) = 4. (For proof see the second Applegate link.)

It appears that there is a relation between this sequence, even superperfect numbers, Mersenne primes and even perfect numbers. Conjecture: The sum of the toothpicks added to the toothpick sieve between the stage A061652(k) and the stage A000668(k) is equal to the k-th even perfect number, for k=1,2,3... For example: A000396(1)= 2+4 =6. A000396(2)= 4+4+8+12 =28. A000396(3)=16+4+8+12+12+16+28+32+20+16+28+36+40+60+88+80 =496. [From Omar E. Pol (info(AT)polprimos.com), May 04 2009]

Concerning this conjecture, see David Applegate's comments on the conjectures in A153006. - N. J. A. Sloane, May 14 2009

In the triangle (See example lines), the sum of row k is equal to A006516(k), for k=1,2,3... [From Omar E. Pol (info(AT)polprimos.com), May 15 2009]

Equals (1, 2, 2, 2,...) convolved with A160762: (1, 0, 2, -2, 2, 2, 2, -6,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 25 2009]

Convolved with the Jacobsthal sequence A001045 = A160704: (1, 3, 9, 19, 41,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 24 2009]

David Applegate, Table of n, a(n) for n = 1..10135

David Applegate, The movie version

David Applegate, Analysis of Omar Pol's Toothpick Sequence A139251

O. E. Pol, Illustration of initial terms of A139251, A160121, A147582 (Overlapping figures) [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

Recurrence from N. J. A. Sloane, Jul 20 2009: a(0) = 0; a(2^i)=2^i for all i; otherwise write n=2^i+j, 0<j<2^i, then a(n) = 2a(j)+a(j+1). Proof: This is a simplification of the following recurrence of David Applegate. QED

Recurrence from David Applegate, Apr 29 2009: (Start)

Write n=2^(i+1)+j, where 0<=j<2^(i+1). Then, for n > 3:

for j=0, a(n) = 2*a(n-2^i) (= n = 2^(i+1))

for 1<=j<=2^i-1, a(n) = a(n-2^i)

for j=2^i, a(n) = a(n-2^i)+4 (= 2^(i+1)+4)

for 2^i+1<=j<=2^(i+1)-2, a(n) = 2*a(n-2^i)+a(n-2^i+1)

for j=2^(i+1)-1, a(n) = 2*a(n-2^i)+a(n-2^i+1)-4

and a(n) = 2^(n-1) for n=1,2,3.

See the link "Analysis of Omar Pol's Toothpick Sequence A139251" for proof. (End)

G.f.: (x/(1+2*x)) * (1 + 2*x*Product(1+x^(2^k-1)+2*x^(2^k),k=0..oo)). - N. J. A. Sloane, May 20 2009, Jun 05 2009

With offset 0 (which would be more natural, but offset 1 is now entrenched): a(0) = 1, a(1) = 2; for i >= 1, a(2^i) = 4; otherwise write n = 2^i +j, 0 < j < 2^i, then a(n) = 2 * Sum_{ k >= 0 } 2^(wt(j+k)-k)*binomial(wt(j+k),k). - N. J. A. Sloane, Jun 03 2009

Triangle begins:

. 1;

. 2,4;

. 4,4,8,12;

. 8,4,8,12,12,16,28,32;

.16,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80;

.32,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80,36,16,28,36,40,60,88,84,56,...

...

G := (x/(1+2*x)) * (1 + 2*x*mul(1+x^(2^k-1)+2*x^(2^k), k=0..20)). - N. J. A. Sloane, May 20 2009, Jun 05 2009

Equals 2*A152968 and 4*A152978 (if we ignore the first couple of terms).

See A147646 for the limiting behavior of the rows.

Cf. A139250, A139252, A139253, A152980, A153000, A153001.

Cf. A000396, A000668, A061652, A153006.

Cf. A006516, A153007, A159790, A001045, A160704, A160762.

Cf. A160121, A147582. [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

Sequence in context: A076340 A076345 A160809 this_sequence A122788 A078003 A081524

Adjacent sequences: A139248 A139249 A139250 this_sequence A139252 A139253 A139254

nonn,tabf,new

Omar E. Pol (info(AT)polprimos.com), Apr 24 2008, Dec 16 2008, Apr 20 2009

The layout of the triangle was adjusted by David Applegate, Apr 29 2009, to reveal that the columns become constant.