

A153000


Toothpick sequence in the first quadrant.


31



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, 95, 105, 120, 142, 162, 170, 171, 173, 176, 179, 183, 190, 198, 203, 207, 214, 223, 233, 248, 270, 290, 299, 303, 310, 319, 329, 344, 366, 387
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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.
At stage 1 we place an orthogonal toothpick of length 2 centered at the end, so a(1) = 1.
In each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end.
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 nth stage. For more information see A139250. (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), 157191


LINKS



FORMULA

G.f.: (1+x)*(Product_{k>=1} (1+x^(2^k1)+2*x^(2^k))1)/((1x)*(1+2*x)).  N. J. A. Sloane, May 20 2009
(End)


MAPLE

G := (1+x)*(mul(1+x^(2^k1)+2*x^(2^k), k=1..20)1)/((1x)*(1+2*x)); # N. J. A. Sloane, May 20 2009


PROG

(Python)
def msb(n):
t=0
while n>>t>0: t+=1
return 2**(t  1)
def a139250(n):
k=(2*msb(n)**2 + 1)//3
return 0 if n==0 else k if n==msb(n) else k + 2*a139250(n  msb(n)) + a139250(n  msb(n) + 1)  1
def a(n): return 0 if n==0 else (a139250(n + 2)  3)//4


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



