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