0,3

A toothpick is a copy of the closed interval [-1,1].

We start at stage 0 with no toothpicks.

At stage 1 we place a toothpick in a horizontal direction, anywhere in the plane.

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.

- Each new toothpick must lie in the X direction or the Y direction

- Two toothpicks may never cross

- Each new toothpick must have its midpoint touching the endpoint of exactly one existing toothpick.

The sequence gives the number of toothpicks after n stages. A139251 (the first differences) gives the number added at the n-th stage.

Call the endpoint of a toothpick "exposed" if it does not touch any other toothpick. At each stage, new toothpicks is placed so their midpoints touch the exposed endpoints.

This is equivalent to a two-dimensional cellular automaton. The animations show the fractal-like behavior.

Observation: It appears that after 2^k-1 steps, there are 2^k exposed endpoints, all located on two lines perpendicular to the initial toothpick. During the following step the 2^k toothpicks are laid on these lines, and only 4 exposed endpoints remain, located at the corners of a square with side length 2^(k-1) times the length of a toothpick. - M. F. Hasler (MHasler(AT)univ-ag.fr), Apr 14 2009 and others. For proof, see the Applegate link "Analysis of Omar Pol's Toothpick Sequence A139251".

In the toothpick sieve we can see patterns related to powers of 2 formed by sequences of rectangles arranged in increasing order and in decreasing order. (See illustrations). [From Omar E. Pol (info(AT)polprimos.com), Apr 20 2009]

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 quarter-turn, and then rotate the whole configuration a quarter turn, we obtain the other configuration.

If the third condition in the definition is changed to "- Each new toothpick must have at 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.

Contribution from Omar E. Pol (info(AT)polprimos.com), May 04 2009: (Start)

A "toothpick" on a square grid can be represented as a square polyedge with 2 components, both on the same line. At the stage n, the toothpick sieve is a polyedge with 2*a(n) components.

It appears that there is a relation between toothpick numbers, Mersenne numbers and Gaussian binomial coefficients. Conjecture: A139250(A000225(k))=A006095(k+1), for k=1,2,3,...

It appears that there is a relation between toothpick numbers, Mersenne numbers and A006516. Conjecture: A139250(A000225(k)) - A139250((A000225(k)-1)/2) = A006516(k), for k=1,2,3,...

It appears that there is a relation between toothpick numbers, Mersenne primes and perfect numbers. Conjecture: A139250(A000668(k)) - A139250((A000668(k)-1)/2) = A000396(k), for k=1,2,3,...), assuming there are no odd perfect numbers. Also we can write A139250(A000668(k)) - A139250((A000668(k)-1)/2) = A000396(n), for k=1,2,3,...)

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 unless an edge (b or c) is <= 2.

It appears that a(2^n) = A007583(n), for n >= 0. (End)

Concerning these conjectures, see David Applegate's comments on the conjectures in A153006. - N. J. A. Sloane, May 14 2009

In the toothpick sieve we can see "canals" and "diffraction patterns". For example, in Applegate's explorer enter a value of N=1008 and click "Update" (See the Applegate link "A139250: the movie version" here). [From Omar E. Pol (info(AT)polprimos.com), May 19 2009]

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 19 2009: (Start)

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,...). (End)

Comment from Benoit Jubin, May 20 2009: The web page "Gallery" of Chris Moore (see link) has some nice pictures which are somewhat similar to the pictures of the present sequence. What sequences do they correspond to?

For connection to Sierpinski triangle and Gould's sequence A001316, see the toothpick triangle A151566. [From Omar E. Pol (info(AT)polprimos.com), May 24 2009]

Equals A160762, (1, 0, 2, -2, 2, 2, 2, -6,...) convolved with 2*n - 1; (1, 3, 5, 7,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 25 2009]

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 25 2009: (Start)

Starting with offset 1 = 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,...] (End)

David Applegate, Table of n, a(n) for n = 0..10135

David Applegate, The movie version

David Applegate, Animation of first 32 stages

David Applegate, Animation of first 64 stages

David Applegate, Animation of first 128 stages

David Applegate, Animation of first 256 stages

David Applegate, C++ program to generate these animations - creates postscript for a specific n

David Applegate, Generates many postscripts, converts them to gifs, and glues the gifs together into an animation

David Applegate, Generates bfiles for A139250, A139251, A147614

David Applegate, The b-files for A139250, A139251, A147614 side-by-side

David Applegate, Analysis of Omar Pol's Toothpick Sequence A139251

Mats Granvik, Jun 21 2009, Additional illustration: Number blocks where each number tells how many times a point on the square grid is crossed or connected to by a toothpick.

M. F. Hasler, Illustration of initial terms

Benoit Jubin, Illustration of initial terms

Chris Moore, Gallery, see the section on David Griffeath's Cellular Automata.

O. E. Pol, Illustration of initial terms

O. E. Pol, Illustration of the toothpick sieve (after 23 steps)

O. E. Pol, Illustration of patterns in the toothpick sieve (after 32 steps)

OEIS Plot 2, Triangular numbers and toothpick numbers vs n [From Omar E. Pol (info(AT)polprimos.com), May 03 2009]

O. E. Pol, OEIS, Plot 2, A000969 and A139250 vs n [From Omar E. Pol (info(AT)polprimos.com), May 23 2009]

Index entries for sequences related to toothpick sequences

Index entries for sequences related to cellular automata

O. E. Pol, Illustration of initial terms of A139250, A160120, A147562 (Overlapping figures) [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

G.f.: (x/((1-x)*(1+2*x))) * (1 + 2*x*Product(1+x^(2^k-1)+2*x^(2^k),k=0..oo)). - N. J. A. Sloane, May 20 2009, Jun 05 2009

For a recurrence (with proof) for the first differences, see the Applegate link "Analysis of Omar Pol's Toothpick Sequence A139251".

Observation: a(n) mod 4 == 3 for n>=2. [From Jaume Oliver Lafont (joliverlafont(AT)gmail.com), Feb 05 2009]

Does a(n)/n^2 have positive lim inf and lim sup? - Benoit Jubin, Apr 15 2009

Answer from David Applegate, May 01 2009: The recursive structure (see A139251) shows that a(2^j) = 2 (4^j-1)/3 + 1. Therefore if 2^j <= n < 2^(j+1), a(n)/n^2 >= a(2^j)/4^(j+1) >= (2 4^j/3) / 4^(j+1) = 1/6 and a(n)/n^2 <= a(2^(j+1)-1)/4^j <= (2 4^(j+1)/3)/4^j = 8/3. To avoid hassles with the -1, I used the fact that a(2^j-1) = a(2^j) - 2^j. These crude bounds can be tightened by observing that a(3 2^j) = 14 (4^j-1)/3 + 9, etc.

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

Contribution from M. F. Hasler (MHasler(AT)univ-ag.fr), Apr 14 2009: (Start)

(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 */,

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 */

c, d, ne, cnt=1); print_all & print1("0, 1"); n<2 & return(n);

for(i=2, n, p=setunion(p, Set(Mat(ee~)[, 1])); /* add endpoints (discard directions) from last move to "used" points */

ne=[]; /* new (exposed) endpoints */

for( k=1, #ee, /* add endpoints of new toothpicks if not among the used points */

setsearch(p, c=ee[k][1]+d=ee[k][2]*I) | ne=setunion(ne, Set([[c, d]])); \\

setsearch(p, c-2*d) | ne=setunion(ne, Set([[c-2*d, -d]]));

); /* useing Set() we have the points sorted, so it's easy to remove those which finally are not exposed because they touch a new toothpick */

forstep( k=#ee=eval(ne), 2, -1, ee[k][1]==ee[k-1][1] & k-- & ee=vecextract(ee, Str("^"k"..", k+1)))\

cnt+=#ee; /* each exposed endpoint will give a new toothpick */ print_all & print1(", "cnt)); cnt} (End)

Cf. A000079, A139251, A139252, A139253, A147614.

Cf. A139560, A152968, A152978, A152980, A152998, A153000, A153001, A153003, A153004, A153006, A153007.

Cf. A000217. [From Omar E. Pol (info(AT)polprimos.com), May 03 2009]

Cf. A007583. [From Omar E. Pol (info(AT)polprimos.com), May 06 2009]

Cf. A007683, A000396, A000225, A000668, A006516, A006095, A019988. [From Omar E. Pol (info(AT)polprimos.com), May 04 2009]

Cf. A160570, A160552 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 19 2009]

Cf. A000969. [From Omar E. Pol (info(AT)polprimos.com), May 23 2009]

Cf. A001316, A151566, A160406, A160408. [From Omar E. Pol (info(AT)polprimos.com), May 24 2009]

Cf. A160702, A078008, A151548, A001045.

Cf. A147562, A160120. [From Omar E. Pol (info(AT)polprimos.com), Nov 02 2009]

Sequence in context: A112714 A160808 A151567 this_sequence A145052 A100900 A117829

Adjacent sequences: A139247 A139248 A139249 this_sequence A139251 A139252 A139253

nonn,new

Omar E. Pol (info(AT)polprimos.com), Apr 24 2008, May 08 2008, Dec 20 2008

Verified and extended using the given PARI code by M. F. Hasler (MHasler(AT)univ-ag.fr), Apr 14 2009

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. Adams-Watters, R. J. Mathar, David W. Wilson, David Applegate, and others.