%I
%S 0,1,3,7,11,15,23,35,43,47,55,67,79,95,123,155,171,175,183,195,207,
%T 223,251,283,303,319,347,383,423,483,571,651,683,687,695,707,719,735,
%U 763,795,815,831,859,895,935,995,1083,1163,1199,1215,1243,1279,1319,1379
%N Toothpick sequence (see Comments lines for definition).
%C A toothpick is a copy of the closed interval [1,1]. (In the paper, we take it to be a copy of the unit interval [1/2, 1/2].)
%C We start at stage 0 with no toothpicks.
%C At stage 1 we place a toothpick in the vertical direction, anywhere in the plane.
%C In general, given a configuration of toothpicks in the plane, at the next stage we add as many toothpicks as possible, subject to certain conditions:
%C  Each new toothpick must lie in the horizontal or vertical directions.
%C  Two toothpicks may never cross.
%C  Each new toothpick must have its midpoint touching the endpoint of exactly one existing toothpick.
%C The sequence gives the number of toothpicks after n stages. A139251 (the first differences) gives the number added at the nth stage.
%C Call the endpoint of a toothpick "exposed" if it does not touch any other toothpick. The growth rule may be expressed as follows: at each stage, new toothpicks are placed so their midpoints touch every exposed endpoint.
%C This is equivalent to a twodimensional cellular automaton. The animations show the fractallike behavior.
%C After 2^k  1 steps, there are 2^k exposed endpoints, all located on two lines perpendicular to the initial toothpick. At the next step, 2^k toothpicks are placed on these lines, leaving only 4 exposed endpoints, located at the corners of a square with side length 2^(k1) times the length of a toothpick.  _M. F. Hasler_, Apr 14 2009 and others. For proof, see the ApplegatePolSloane paper.
%C If the third condition in the definition is changed to " Each new toothpick must have at exactly one of its endpoints touching the midpoint of an existing toothpick" then the same sequence is obtained. The configurations of toothpicks are of course different from those in the present sequence. But if we start with the configurations of the present sequence, rotate each toothpick a quarterturn, and then rotate the whole configuration a quarterturn, we obtain the other configuration.
%C If the third condition in the definition is changed to " Each new toothpick must have at least one of its endpoints touching the midpoint of an existing toothpick" then the sequence n^2  n + 1 is obtained, because there are no holes left in the grid.
%C A "toothpick" of length 2 can be regarded as a polyedge with 2 components, both on the same line. At stage n, the toothpick structure is a polyedge with 2*a(n) components.
%C Conjecture: Consider the rectangles in the sieve (including the squares). The area of each rectangle (A = b*c) and the edges (b and c) are powers of 2, but at least one of the edges (b or c) is <= 2.
%C In the toothpick structure, if n >> 1, we can see some patterns that look like "canals" and "diffraction patterns". For example, see the Applegate link "A139250: the movie version", then enter n=1008 and click "Update". See also "Tsquare (fractal)" in the Links section.  _Omar E. Pol_, May 19 2009, Oct 01 2011
%C From _Benoit Jubin_, May 20 2009: The web page "Gallery" of Chris Moore (see link) has some nice pictures that are somewhat similar to the pictures of the present sequence. What sequences do they correspond to?
%C For a connection to SierpiĆski triangle and Gould's sequence A001316, see the leftist toothpick triangle A151566.
%C _Eric Rowland_ comments on Mar 15 2010 that this toothpick structure can be represented as a 5state CA on the square grid. On Mar 18 2010, _David Applegate_ showed that three states are enough. See links.
%C Equals row sums of triangle A160570 starting with offset 1; equivalent to convolving A160552: (1, 1, 3, 1, 3, 5, 7, ...) with (1, 2, 2, 2, ...). Equals A160762: (1, 0, 2, 2, 2, 2, 2, 6, ...) convolved with 2*n  1: (1, 3, 5, 7, ...). Starting with offset 1 equals A151548: [1, 3, 5, 7, 5, 11, 17, 15, ...] convolved with A078008 signed (A151575): [1, 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, ...].  _Gary W. Adamson_, May 19 2009, May 25 2009
%C For a threedimensional version of the toothpick structure, see A160160.  _Omar E. Pol_, Dec 06 2009
%C From _Omar E. Pol_, May 20 2010: (Start)
%C Observation about the arrangement of rectangles:
%C It appears there is a nice pattern formed by distinct modular substructures: a central cross surrounded by asymmetrical crosses (or "hidden crosses") of distinct sizes and also by "nuclei" of crosses.
%C Conjectures: after 2^k stages, for k >= 2, and for m = 1 to k  1, there are 4^(m1) substructures of size s = k  m, where every substructure has 4*s rectangles. The total number of substructures is equal to (4^(k1)1)/3 = A002450(k1). For example: If k = 5 (after 32 stages) we can see that:
%C a) There is a central cross, of size 4, with 16 rectangles.
%C b) There are four hidden crosses, of size 3, where every cross has 12 rectangles.
%C c) There are 16 hidden crosses, of size 2, where every cross has 8 rectangles.
%C d) There are 64 nuclei of crosses, of size 1, where every nucleus has 4 rectangles.
%C Hence the total number of substructures after 32 stages is equal to 85. Note that in every arm of every substructure, in the potential growth direction, the length of the rectangles are the powers of 2. (See illustrations in the links. See also A160124.) (End)
%C It appears that the number of grid points that are covered after nth stage of the toothpick structure, assuming the toothpicks have length 2*k, is equal to (2*k2)*a(n) + A147614(n), k > 0. See the formulas of A160420 and A160422.  _Omar E. Pol_, Nov 13 2010
%C Version "Gullwing": on the semiinfinite square grid, at stage 1, we place a horizontal "gull" with its vertices at [(1, 2), (0, 1), (1, 2)]. At stage 2, we place two vertical gulls. At stage 3, we place four horizontal gulls. a(n) is also the number of gulls after nth stage. For more information about the growth of gulls see A187220.  _Omar E. Pol_, Mar 10 2011
%C From _Omar E. Pol_, Mar 12 2011: (Start)
%C Version "Itoothpick": we define an "Itoothpick" to consist of two connected toothpicks, as a bar of length 2. An Itoothpick with length 2 is formed by two toothpicks with length 1. The midpoint of an Itoothpick is touched by its two toothpicks. a(n) is also the number of Itoothpicks after nth stage in the Itoothpick structure. The Itoothpick structure is essentially the original toothpick structure in which every toothpick is replaced by an Itoothpick. Note that in the physical model of the original toothpick structure the midpoint of a wooden toothpick of the new generation is superimposed on the endpoint of a wooden toothpick of the old generation. However, in the physical model of the Itoothpick structure the wooden toothpicks are not overlapping because all wooden toothpicks are connected by their endpoints. For the number of toothpicks in the Itoothpick structure see A160164 which also gives the number of gullwing in a gullwing structure because the gullwing structure of A160164 is equivalent to the Itoothpick structure. It also appears that the gullwing sequence A187220 is a supersequence of the original toothpick sequence A139250 (this sequence).
%C For the connection with the UlamWarburton cellular automaton see the ApplegatePolSloane paper and see also A160164 and A187220.
%C (End)
%C A version in which the toothpicks are connected by their endpoints: on the semiinfinite square grid, at stage 1, we place a vertical toothpick of length 1 from (0, 0). At stage 2, we place two horizontal toothpicks from (0,1), and so on. The arrangement looks like half of the Itoothpick structure. a(n) is also the number of toothpicks after the nth.  _Omar E. Pol_, Mar 13 2011
%C Version "Quartercircle" (or Qtoothpick): a(n) is also the number of Qtoothpicks after the nth stage in a Qtoothpick structure in the first quadrant. We start from (0,1) with the first Qtoothpick centered at (1, 1). The structure is asymmetric. For a similar structure but starting from (0, 0) see A187212. See A187210 and A187220 for more information.  _Omar E. Pol_, Mar 22 2011
%C Version "Tree": It appears that a(n) is also the number of toothpicks after the nth stage in a toothpick structure constructed following a special rule: the toothpicks of the new generation have length 4 when they are placed on the infinite square grid (note that every toothpick has four components of length 1), but after every stage, one (or two) of the four components of every toothpick of the new generation is removed, if such component contains an endpoint of the toothpick and if such endpoint is touching the midpoint or the endpoint of another toothpick. The truncated endpoints of the toothpicks remain exposed forever. Note that there are three sizes of toothpicks in the structure: toothpicks of lengths 4, 3 and 2. A159795 gives the total number of components in the structure after the nth stage. A153006 (the corner sequence of the original version) gives 1/4 of the total of components in the structure after the nth stage.  _Omar E. Pol_, Oct 24 2011
%C From _Omar E. Pol_, Sep 16 2012: (Start)
%C It appears that a(n)/A147614(n) converges to 3/4.
%C It appears that a(n)/A160124(n) converges to 3/2.
%C It appears that a(n)/A139252(n) converges to 3.
%C Also:
%C It appears that A147614(n)/A160124(n) converges to 2.
%C It appears that A160124(n)/A139252(n) converges to 2.
%C It appears that A147614(n)/A139252(n) converges to 4.
%C (End)
%C It appears that a(n) is also the total number of ON cells after nth stage in a quadrant of the structure of the cellular automaton described in A169707 plus the total number of ON cells after n+1 stages in a quadrant of the mentioned structure, without its central cell. See the illustration of the NWNESESW version in A169707. See also the connection between A160164 and A169707.  _Omar E. Pol_, Jul 26 2015
%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), 157191
%D L. D. Pryor, The Inheritance of Inflorescence Characters in Eucalyptus, Proceedings of the Linnean Society of New South Wales, V. 79, (1954), p. 81, 83.
%D Richard P. Stanley, Enumerative Combinatorics, volume 1, second edition, chapter 1, exercise 95, figure 1.28, Cambridge University Press (2012), p. 120, 166.
%H N. J. A. Sloane, <a href="/A139250/b139250.txt">Table of n, a(n) for n = 0..65535</a>
%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>
%H David Applegate, <a href="/A139250/a139250.anim.32.gif">Animation of first 32 stages</a>
%H David Applegate, <a href="/A139250/a139250.anim.64.gif">Animation of first 64 stages</a>
%H David Applegate, <a href="/A139250/a139250.anim.128.gif">Animation of first 128 stages</a>
%H David Applegate, <a href="/A139250/a139250.anim.256.gif">Animation of first 256 stages</a>
%H David Applegate, <a href="/A139250/a139250ps.cc">C++ program to generate these animations  creates postscript for a specific n</a>
%H David Applegate, <a href="/A139250/a139250_gengif.txt">Generates many postscripts, converts them to gifs, and glues the gifs together into an animation</a>
%H David Applegate, <a href="/A139250/a139250_bfiles.cc">Generates bfiles for A139250, A139251, A147614</a>
%H David Applegate, <a href="/A139250/a139250_b.txt">The bfiles for A139250, A139251, A147614 sidebyside</a>
%H David Applegate, <a href="/A139250/a139250_3state.txt">A threestate CA for the toothpick structure</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>, which is also available at <a href="http://arxiv.org/abs/1004.3036">arXiv:1004.3036v2</a>
%H Joe Champion, <a href="http://boisemathcircles.org/bmcsessions/toothpicks">Ultimate toothpick pattern</a>, <a href="http://web.archive.org/web/20171110234607/http://i1.wp.com/boisemathcircles.org/wpcontent/uploads/2015/09/IMG_0004.jpg">Photo 1</a>, <a href="http://web.archive.org/web/20171110234732/http://i2.wp.com/boisemathcircles.org/wpcontent/uploads/2015/09/IMG_0003.jpg">Photo 2</a>, <a href="http://web.archive.org/web/20171110234538/http://i2.wp.com/boisemathcircles.org/wpcontent/uploads/2015/09/IMG_0006.jpg">Photo 3</a>, <a href="http://web.archive.org/web/20171110234402/http://i1.wp.com/boisemathcircles.org/wpcontent/uploads/2015/09/IMG_0005.jpg">Photo 4</a>, Boise Math Circles, Boise State University. [Links updated by _P. Michael Hutchins_, Mar 03 2018]
%H Barry Cipra, <a href="http://home.gwu.edu/~maxal/943.pdf">What comes next?</a>, Science (AAAS) 327: 943.
%H Steven R. Finch, <a href="/A139250/a139250_1.pdf">Toothpicks and Live Cells</a>, July 21, 2015. [Cached copy, with permission of the author]
%H Ulrich Gehmann, Martin Reiche, <a href="http://dump.artofdata.de/wmm_book_hq.pdf">World mountain machine</a>, Berlin, (2014), first edition, p. 205, 238, 253.
%H Mats Granvik, <a href="/A139250/a139250c.jpg">Additional illustration</a>: Number blocks where each number tells how many times a point on the square grid is crossed or connected to by a toothpick, Jun 21 2009.
%H Gordon Hamilton, <a href="http://youtu.be/7efCz2FvUDI">Three integer sequences from recreational mathematics</a>, Video (2013?).
%H M. F. Hasler, <a href="/A139250/a139250.pdf">Illustration of initial terms</a>
%H M. F. Hasler, <a href="http://docs.google.com/Presentation?id=d34bxwj_236hcjnm6dc">Illustrations (Three slides)</a>
%H Brian Hayes, <a href="http://bitplayer.org/2013/joshuatreesandtoothpicks">Joshua Trees and Toothpicks</a>
%H Brian Hayes, <a href="/A139250/a139250_Hayes.png">Idealized Joshua tree</a>, a figure from "Joshua Trees and Toothpicks" (see preceding link)
%H Brian Hayes, <a href="http://bitplayer.org/extras/toothpicks/toothpicks.html">The Toothpick Sequence  BitPlayer</a>
%H Benoit Jubin, <a href="/A139250/a139250.txt">Illustration of initial terms</a>
%H Chris Moore, <a href="http://www.santafe.edu/~moore/gallery.html">Gallery</a>, see the section on David Griffeath's Cellular Automata.
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp4d4.jpg">Illustration of initial terms</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp6d4.jpg">Illustration of initial terms using "gulls" (or Gtoothpicks)</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp7d4.jpg">Illustration of initial terms using quatercircles (or Qtoothpicks)</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp283.jpg">Illustration of the toothpick structure (after 23 steps)</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp683.jpg">Illustration of patterns in the toothpick structure (after 32 steps)</a>
%H Omar E. Pol, <a href="/A139250/a139250.jpg">Illustration of patterns in the toothpick structure (after 32 steps)</a> [Cached copy, with permission]
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca001.jpg">Illustration of initial terms of A139250, A160120, A147562 (Overlapping figures)</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp120.jpg">Illustration of initial terms of A160120, A161206, A161328, A161330 (triangular grid and toothpick structure)</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp684.jpg">Illustration of the substructures in the first quadrant (As pieces of a puzzle), after 32 stages</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poltp685.jpg">Illustration of the potential growth direction of the arms of the substructures, after 32 stages</a>
%H Programing Puzzles & Code Golf Stack Exchange, <a href="http://codegolf.stackexchange.com/questions/64650/generatetoothpicksequence">Generate toothpick sequence</a>
%H L. D. Pryor, <a href="http://www.biodiversitylibrary.org/item/108709#page/155/mode/1up">Illustration of initial terms (Fig. 2a)</a>
%H L. D. Pryor, <a href="http://www.biodiversitylibrary.org/item/108709#page/151/mode/1up">The Inheritance of Inflorescence Characters in Eucalyptus</a>, Proceedings of the Linnean Society of New South Wales, V. 79, (1954), p. 7989.
%H E. Rowland, <a href="/A139250/a139250_Rowland.txt">Toothpick sequence from cellular automaton on square grid</a>
%H E. Rowland, <a href="/A139250/a139250_Rowland.jpg">Initial stages of toothpick sequence from cellular automaton on square grid (includes Mathematica code)</a>
%H K. Ryde, <a href="http://search.cpan.org/~kryde/MathPlanePathToothpick18/lib/Math/PlanePath/ToothpickTree.pm">ToothpickTree</a>.
%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 Alex van den Brandhof and Paul Levrie, <a href="http://www.pyth.eu/jaargangen/Pyth556.pdf">Tandenstokerrij</a>, Pythagoras, Viskundetijdschrift voor Jongeren, 55ste Jaargang, Nummer 6, Juni 2016, (see the cover, pages 1, 18, 19 and the back cover).
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/H_tree">H tree</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Toothpick_sequence">Toothpick sequence</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Tsquare_(fractal)">Tsquare (fractal)</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(2^k) = A007583(k), if k >= 0.
%F a(2^k1) = A006095(k+1), if k >= 1.
%F a(A000225(k))  a((A000225(k)1)/2) = A006516(k), if k >= 1.
%F a(A000668(k))  a((A000668(k)1)/2) = A000396(k), if k >= 1.
%F G.f.: (x/((1x)*(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 One can show that lim sup a(n)/n^2 = 2/3, and it appears that lim inf a(n)/n^2 is 0.451...  _Benoit Jubin_, Apr 15 2009 and Jan 29 2010, _N. J. A. Sloane_, Jan 29 2010
%F Observation: a(n) mod 4 == 3 for n>=2.  _Jaume Oliver Lafont_, Feb 05 2009
%F a(2^k1) = A000969(2^k2), if k >= 1.  _Omar E. Pol_, Feb 13 2010
%F It appears that a(n) = (A187220(n+1)  1)/2.  _Omar E. Pol_, Mar 08 2011
%F a(n) = 4*A153000(n2) + 3, if n >= 2.  _Omar E. Pol_, Oct 01 2011
%F It appears that a(n) = A160552(n) + (A169707(n)  1)/2, n >= 1.  _Omar E. Pol_, Feb 15 2015
%F It appears that a(n) = A255747(n) + A255747(n1), n >= 1.  _Omar E. Pol_, Mar 16 2015
%F Let n = msb(n) + j where msb(n) = A053644(n) and let a(0) = 0. Then a(n) = (2 * msb(n)^2 + 1) / 3 + 2 * a(j) + a(j + 1)  1.  _David A. Corneth_, Mar 26 2015
%F It appears that a(n) = (A169707(n)  1)/4 + (A169707(n+1)  1)/4, n >= 1.  _Omar E. Pol_, Jul 24 2015
%e a(10^10) = 52010594272060810683  _David A. Corneth_, Mar 26 2015
%p G := (x/((1x)*(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/((1  x)*(1 + 2x))) (1 + 2x*Product[1 + x^(2^k  1) + 2*x^(2^k), {k, 0, 20}]), {x, 0, 53}], x] (* _Robert G. Wilson v_, Dec 06 2010 *)
%o (PARI) A139250(n,print_all=0)={my(p=[] /* set of "used" points. Points are written as complex numbers, c=x+iy. Toothpicks are of length 2 */,
%o ee=[[0,1]] /* list of (exposed) endpoints. Exposed endpoints are listed as [c,d] where c=x+iy is the position of the endpoint, and d (unimodular) is the direction */
%o c,d,ne, cnt=1); print_all && print1("0,1"); n<2 && return(n);
%o for(i=2,n, p=setunion(p, Set(Mat(ee~)[,1])); /* add endpoints (discard directions) from last move to "used" points */
%o ne=[]; /* new (exposed) endpoints */
%o for( k=1, #ee, /* add endpoints of new toothpicks if not among the used points */
%o setsearch(p, c=ee[k][1]+d=ee[k][2]*I)  ne=setunion(ne,Set([[c,d]]));\\
%o setsearch(p, c2*d)  ne=setunion(ne,Set([[c2*d,d]]));
%o ); /* using Set() we have the points sorted, so it's easy to remove those which finally are not exposed because they touch a new toothpick */
%o forstep( k=#ee=eval(ne), 2, 1, ee[k][1]==ee[k1][1] && k && ee=vecextract(ee,Str("^"k"..",k+1)))\
%o cnt+=#ee; /* each exposed endpoint will give a new toothpick */ print_all && print1(","cnt));cnt} \\ _M. F. Hasler_, Apr 14 2009
%o (PARI)
%o \\works for n > 0
%o a(n) = {my(k = (2*msb(n)^2 + 1) / 3); if(n==msb(n),k , k + 2*a(nmsb(n)) + a(n  msb(n) + 1)  1)}
%o msb(n)=my(t=0);while(n>>t>0,t++);2^(t1)\\ _David A. Corneth_, Mar 26 2015
%o (Python)
%o def msb(n):
%o t=0
%o while n>>t>0: t+=1
%o return 2**(t  1)
%o def a(n):
%o k=(2*msb(n)**2 + 1)/3
%o return 0 if n==0 else k if n==msb(n) else k + 2*a(n  msb(n)) + a(n  msb(n) + 1)  1
%o print [a(n) for n in xrange(101)] # _Indranil Ghosh_, Jul 01 2017, after _David A. Corneth_'s PARI script
%Y Cf. A000079, A139251, A139252, A139253, A147614, A139560, A152968, A152978, A152980, A152998, A153000, A153001, A153003, A153004, A153006, A153007, A000217, A007583, A007683, A000396, A000225, A000668, A006516, A006095, A019988, A160570, A160552, A000969, A001316, A151566, A160406, A160408, A160702, A078008, A151548, A001045, A147562, A160120, A160160, A160170, A160172, A161206, A161328, A161330, A002450, A160124.
%K nonn,look,changed
%O 0,3
%A _Omar E. Pol_, Apr 24 2008
%E Verified and extended, a(49)a(53), using the given PARI code by _M. F. Hasler_, Apr 14 2009
%E Edited by _N. J. A. Sloane_, Apr 29 2009, incorporating comments from _Omar E. Pol_, _M. F. Hasler_, _Rob Pratt_, _Jaume Oliver Lafont_, _Franklin T. AdamsWatters_, _R. J. Mathar_, _David W. Wilson_, _David Applegate_, _Benoit Jubin_ and others.
%E Further edited by _N. J. A. Sloane_, Jan 28 2010
