login
Toothpick sequence in the first quadrant.
31

%I #49 Mar 12 2021 07:51:19

%S 0,1,2,3,5,8,10,11,13,16,19,23,30,38,42,43,45,48,51,55,62,70,75,79,86,

%T 95,105,120,142,162,170,171,173,176,179,183,190,198,203,207,214,223,

%U 233,248,270,290,299,303,310,319,329,344,366,387

%N Toothpick sequence in the first quadrant.

%C From _Omar E. Pol_, Nov 29 2009: (Start)

%C At stage 0, we start from a horizontal half toothpick at [(0,1),(1,1)]. This half toothpick represents one of the two components of the second toothpick placed in the toothpick structure of A139250. Consider only the toothpicks of length 2, so a(0) = 0.

%C At stage 1 we place an orthogonal toothpick of length 2 centered at the end, so a(1) = 1.

%C In each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end.

%C The sequence gives the number of toothpicks after n stages. Note that this sequence contains even numbers and odd numbers, the same as A152978 (the first differences) which gives the number of toothpicks added at n-th stage. For more information see A139250. (End)

%C A079559 gives the parity of this sequence, if n >= 1. - _Omar E. Pol_, Aug 13 2013

%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 David Applegate, <a href="/A139250/a139250.anim.html">The movie version</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 Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp016.jpg">Illustration of initial terms</a> [From Omar E. Pol, Nov 29 2009]

%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>

%H <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F a(n) = (A139250(n+2)-3)/4 = (A152998(n+1)-1)/2.

%F G.f.: (1+x)*(Product_{k>=1} (1+x^(2^k-1)+2*x^(2^k))-1)/((1-x)*(1+2*x)). - _N. J. A. Sloane_, May 20 2009

%F Contribution from _Omar E. Pol_, Oct 01 2011: (Start)

%F a(n) = A152998(n+1) + A153003(n+1) - A139250(n+2) + 1.

%F a(n) = A139250(n+2) - A153003(n+1) - 2.

%F a(n) = A153003(n+1) - A152998(n+1).

%F (End)

%F a(n) = (A187220(n+3) - 7)/8. - _Omar E. Pol_, Feb 16 2013

%p G := (1+x)*(mul(1+x^(2^k-1)+2*x^(2^k),k=1..20)-1)/((1-x)*(1+2*x)); # _N. J. A. Sloane_, May 20 2009

%o (Python)

%o def msb(n):

%o t=0

%o while n>>t>0: t+=1

%o return 2**(t - 1)

%o def a139250(n):

%o k=(2*msb(n)**2 + 1)//3

%o return 0 if n==0 else k if n==msb(n) else k + 2*a139250(n - msb(n)) + a139250(n - msb(n) + 1) - 1

%o def a(n): return 0 if n==0 else (a139250(n + 2) - 3)//4

%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jul 01 2017

%Y Cf. A139250, A139251, A152978, A153006.

%Y Cf. A152998, A160406. - _Omar E. Pol_, Nov 29 2009

%K nonn

%O 0,3

%A _Omar E. Pol_, Dec 16 2008, Dec 20 2008, Jan 02 2009