%I
%S 0,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,
%T 36,40,60,88,80,32,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80,36,16,
%U 28,36,40,60,88,84,56,60,92,112,140,208,256,192,64,4,8,12,12,16,28,32,20,16,28
%N First differences of toothpicks numbers A139250.
%C Number of toothpicks added to the toothpick structure at the nth step (see A139250).
%C 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.)
%C 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 structure between the stage A061652(k) and the stage A000668(k) is equal to the kth even perfect number, for k >= 1. 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_, May 04 2009]
%C Concerning this conjecture, see _David Applegate_'s comments on the conjectures in A153006.  _N. J. A. Sloane_, May 14 2009
%C In the triangle (See example lines), the sum of row k is equal to A006516(k), for k >= 1. [From _Omar E. Pol_, May 15 2009]
%C Equals (1, 2, 2, 2,...) convolved with A160762: (1, 0, 2, 2, 2, 2, 2, 6,...). [From _Gary W. Adamson_, May 25 2009]
%C Convolved with the Jacobsthal sequence A001045 = A160704: (1, 3, 9, 19, 41,...). [From _Gary W. Adamson_, May 24 2009]
%H N. J. A. Sloane, <a href="/A139251/b139251.txt">Table of n, a(n) for n = 0..65535</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157191
%H David Applegate, <a href="http://www.research.att.com/~david/oeis/toothpick.html">The movie version</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca002.jpg">Illustration of initial terms of A139251, A160121, A147582 (Overlapping figures)</a> [From _Omar E. Pol_, Nov 02 2009]
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/toothlist.html">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%F 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
%F Recurrence from _David Applegate_, Apr 29 2009: (Start)
%F Write n=2^(i+1)+j, where 0<=j<2^(i+1). Then, for n > 3:
%F for j=0, a(n) = 2*a(n2^i) (= n = 2^(i+1))
%F for 1<=j<=2^i1, a(n) = a(n2^i)
%F for j=2^i, a(n) = a(n2^i)+4 (= 2^(i+1)+4)
%F for 2^i+1<=j<=2^(i+1)2, a(n) = 2*a(n2^i)+a(n2^i+1)
%F for j=2^(i+1)1, a(n) = 2*a(n2^i)+a(n2^i+1)4
%F and a(n) = 2^(n1) for n=1,2,3. (End)
%F G.f.: (x/(1+2*x)) * (1 + 2*x*Product(1+x^(2^k1)+2*x^(2^k),k=0..oo)).  _N. J. A. Sloane_, May 20 2009, Jun 05 2009
%F 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
%F It appears that a(n) = A187221(n+1)/2.  Omar E. Pol, Mar 08 2011.
%e Triangle begins:
%e . 0;
%e . 1;
%e . 2,4;
%e . 4,4,8,12;
%e . 8,4,8,12,12,16,28,32;
%e .16,4,8,12,12,16,28,32,20,16,28,36,40,60,88,80;
%e .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,...
%e ...
%e The row sums give A006516.
%p G := (x/(1+2*x)) * (1 + 2*x*mul(1+x^(2^k1)+2*x^(2^k),k=0..20)).  _N. J. A. Sloane_, May 20 2009, Jun 05 2009
%p # From _N. J. A. Sloane_, Dec 25, 2009: A139250 is T, A139251 is a.
%p a:=[0,1,2,4]; T:=[0,1,3,7]; M:=10;
%p for k from 1 to M do
%p a:=[op(a),2^(k+1)];
%p T:=[op(T),T[nops(T)]+a[nops(a)]];
%p for j from 1 to 2^(k+1)1 do
%p a:=[op(a), 2*a[j+1]+a[j+2]];
%p T:=[op(T),T[nops(T)]+a[nops(a)]];
%p od: od: a; T;
%t CoefficientList[Series[((x  x^2)/((1  x) (1 + 2 x))) (1 + 2 x Product[1 + x^(2^k  1) + 2 x^(2^k), {k, 0, 20}]), {x, 0, 60}], x] (* _Vincenzo Librandi_, Aug 22 2014 *)
%Y Equals 2*A152968 and 4*A152978 (if we ignore the first couple of terms).
%Y See A147646 for the limiting behavior of the rows. See also A006516.
%Y Row lengths in A011782.
%Y Cf. A139250, A139252, A139253, A152980, A153000, A153001, A000396, A000668, A061652, A153006.
%Y Cf. A006516, A153007, A159790, A001045, A160704, A160762, A160121, A147582.
%K nonn,tabf
%O 0,3
%A _Omar E. Pol_, Apr 24 2008, Dec 16 2008, Apr 20 2009
%E The layout of the triangle was adjusted by _David Applegate_, Apr 29 2009, to reveal that the columns become constant.
