cp's OEIS Frontend

The "word" of this cellular automaton is abcb.

The associated sound to the animation of this cellular automaton could be [tick, tock, tack, tock], [tick, tock, tack, tock], and so on.

For more information about the "word" of a cellular automaton see A296612.

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].)

We start at stage 0 with no toothpicks.

At stage 1 we place a toothpick in the vertical 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 horizontal or vertical directions.

- 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. The growth rule may be expressed as follows: at each stage, new toothpicks are placed so their midpoints touch every exposed endpoint.

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

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^(k-1) times the length of a toothpick. - M. F. Hasler, Apr 14 2009 and others. For proof, see the Applegate-Pol-Sloane paper.

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

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.

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.

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 "T-square (fractal)" in the Links section. - Omar E. Pol, May 19 2009, Oct 01 2011

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?

For a connection to Sierpiński triangle and Gould's sequence A001316, see the leftist toothpick triangle A151566.

Eric Rowland comments on Mar 15 2010 that this toothpick structure can be represented as a 5-state CA on the square grid. On Mar 18 2010, David Applegate showed that three states are enough. See links.

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

For a three-dimensional version of the toothpick structure, see A160160. - Omar E. Pol, Dec 06 2009

From Omar E. Pol, May 20 2010: (Start)

Observation about the arrangement of rectangles:

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.

Conjectures: after 2^k stages, for k >= 2, and for m = 1 to k - 1, there are 4^(m-1) substructures of size s = k - m, where every substructure has 4*s rectangles. The total number of substructures is equal to (4^(k-1)-1)/3 = A002450(k-1). For example: If k = 5 (after 32 stages) we can see that:

a) There is a central cross, of size 4, with 16 rectangles.

b) There are four hidden crosses, of size 3, where every cross has 12 rectangles.

c) There are 16 hidden crosses, of size 2, where every cross has 8 rectangles.

d) There are 64 nuclei of crosses, of size 1, where every nucleus has 4 rectangles.

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)

It appears that the number of grid points that are covered after n-th stage of the toothpick structure, assuming the toothpicks have length 2*k, is equal to (2*k-2)*a(n) + A147614(n), k > 0. See the formulas of A160420 and A160422. - Omar E. Pol, Nov 13 2010

Version "Gullwing": on the semi-infinite 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 n-th stage. For more information about the growth of gulls see A187220. - Omar E. Pol, Mar 10 2011

From Omar E. Pol, Mar 12 2011: (Start)

Version "I-toothpick": we define an "I-toothpick" to consist of two connected toothpicks, as a bar of length 2. An I-toothpick with length 2 is formed by two toothpicks with length 1. The midpoint of an I-toothpick is touched by its two toothpicks. a(n) is also the number of I-toothpicks after n-th stage in the I-toothpick structure. The I-toothpick structure is essentially the original toothpick structure in which every toothpick is replaced by an I-toothpick. 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 I-toothpick structure the wooden toothpicks are not overlapping because all wooden toothpicks are connected by their endpoints. For the number of toothpicks in the I-toothpick structure see A160164 which also gives the number of gullwing in a gullwing structure because the gullwing structure of A160164 is equivalent to the I-toothpick structure. It also appears that the gullwing sequence A187220 is a supersequence of the original toothpick sequence A139250 (this sequence).

For the connection with the Ulam-Warburton cellular automaton see the Applegate-Pol-Sloane paper and see also A160164 and A187220.

(End)

A version in which the toothpicks are connected by their endpoints: on the semi-infinite 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 I-toothpick structure. a(n) is also the number of toothpicks after the n-th. - Omar E. Pol, Mar 13 2011

Version "Quarter-circle" (or Q-toothpick): a(n) is also the number of Q-toothpicks after the n-th stage in a Q-toothpick structure in the first quadrant. We start from (0,1) with the first Q-toothpick 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

Version "Tree": It appears that a(n) is also the number of toothpicks after the n-th 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 n-th stage. A153006 (the corner sequence of the original version) gives 1/4 of the total of components in the structure after the n-th stage. - Omar E. Pol, Oct 24 2011

From Omar E. Pol, Sep 16 2012: (Start)

It appears that a(n)/A147614(n) converges to 3/4.

It appears that a(n)/A160124(n) converges to 3/2.

It appears that a(n)/A139252(n) converges to 3.

Also:

It appears that A147614(n)/A160124(n) converges to 2.

It appears that A160124(n)/A139252(n) converges to 2.

It appears that A147614(n)/A139252(n) converges to 4.

(End)

It appears that a(n) is also the total number of ON cells after n-th 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 NW-NE-SE-SW version in A169707. See also the connection between A160164 and A169707. - Omar E. Pol, Jul 26 2015

On the infinite Cairo pentagonal tiling consider the symmetric figure formed by two non-adjacent pentagons connected by a line segment joining two trivalent nodes. At stage 1 we start with one of these figures turned ON. The rule for the next stages is that the concave part of the figures of the new generation must be adjacent to the complementary convex part of the figures of the old generation. a(n) gives the number of figures that are ON in the structure after n-th stage. A160164(n) gives the number of ON cells in the structure after n-th stage. - Omar E. Pol, Mar 29 2018

From Omar E. Pol, Mar 06 2019: (Start)

The "word" of this sequence is "ab". For further information about the word of cellular automata see A296612.

Version "triangular grid": a(n) is also the total number of toothpicks of length 2 after n-th stage in the toothpick structure on the infinite triangular grid, if we use only two of the three axes. Otherwise, if we use the three axes, so we have the sequence A296510 which has word "abc".

The normal toothpick structure can be considered a superstructure of the Ulam-Warburton celular automaton since A147562(n) equals here the total number of "hidden crosses" after 4*n stages, including the central cross (beginning to count the crosses when their "nuclei" are totally formed with 4 quadrilaterals). Note that every quadrilateral in the structure belongs to a "hidden cross".

Also, the number of "hidden crosses" after n stages equals the total number of "flowers with six petals" after n-th stage in the structure of A323650, which appears to be a "missing link" between this sequence and A147562.

Note that the location of the "nuclei of the hidden crosses" is very similar (essentially the same) to the location of the "flowers with six petals" in the structure of A323650 and to the location of the "ON" cells in the version "one-step bishop" of the Ulam-Warburton cellular automaton of A147562. (End)

From Omar E. Pol, Nov 27 2020: (Start)

The simplest substructures are the arms of the hidden crosses. Each closed region (square or rectangle) of the structure belongs to one of these arms. The narrow arms have regions of area 1, 2, 4, 8, ... The broad arms have regions of area 2, 4, 8, 16 , ... Note that after 2^k stages, with k >= 3, the narrow arms of the main hidden crosses in each quadrant frame the size of the toothpick structure after 2^(k-1) stages.

Another kind of substructure could be called "bar chart" or "bar graph". This substructure is formed by the rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure after 2^k stages, with k >= 2. The height of these successive regions gives the first 2^(k-1) - 1 terms from A006519. For example: if k = 5 the respective heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1]. The area of these successive regions gives the first 2^(k-1) - 1 terms of A171977. For example: if k = 5 the respective areas are [2, 4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2].

For a connection to Mersenne primes (A000668) and perfect numbers (A000396) see A153006.

For a representation of the Wagstaff primes (A000979) using the toothpick structure see A194810.

For a connection to stained glass windows and a hidden curve see A336532. (End)

It appears that the graph of a(n) bears a striking resemblance to the cumulative distribution function F(x) for X the random variable taking values in [0,1], where the binary expansion of X is given by a sequence of independent coin tosses with probability 3/4 of being 1 at each bit. It appears that F(n/2^k)*(2^(2k+1)+1)/3 approaches a(n) for k large. - James Coe, Jan 10 2022

Also, at least for the first five columns, column k gives the row lengths of the irregular triangles of the first differences of the total number of elements in the structure of some cellular automata. Indeed, the study of the structure and the behavior of the toothpick cellular automaton on triangular grid (A296510), and other C.A. of the same family, reveals that some cellular automata that have recurrent periods can be represented by irregular triangles (of first differences) whose row lengths are the terms of A011782 multiplied by k (instead of powers of 2), where k is the length of an internal cycle. This internal cycle is called here "word" of a cellular automaton (see examples).

We use toothpicks of length 2, the same as the toothpick cellular automaton of A139250, but here we are on triangular grid, hence we have three axes, not two.

The Toothpicks are alternately arranged on the three axes in a rotating cycle.

a(n) gives the number of toothpicks in the structure after n-th stage.

A296511 (the first differences) gives the number of toothpicks added at n-th stage.

The structure reveals that some cellular automata that have recurrent periods can be represented by irregular triangles of first differences whose row lengths are the terms of A011782 multiplied by k (instead of powers of 2), where k is the length of their "word". In this case the word should be "abc", therefore k = 3. In the case of the cellular automaton with normal toothpicks (A139250) the word should be "ab", therefore k = 2.

For more information about the "word" of a cellular automaton see A296612.

Note that due to the unusual orientation of the polygons that are located on the edges of the structure, the image of this cellular automaton resembles the photo of an object that is rotating.

Note that between other polygons the structure contains the same "petals" as the floret pentagonal tiling.

Apparently the graph could be similar to the graph of A151907.

a(n) gives the number of toothpicks of length 2 in the structure after n-th stage.

A299479 (the first differences) gives the number of toothpicks added at n-th stage.

For more information about the "word" of a cellular automaton see A296612.

An idea from Jean Hoffmann.

In this cellular automaton a V-toothpick is formed by 2 toothpicks of length 1 that share a vertex and the angle between both toothpicks is 60 degrees.

On the infinite triangular grid we start with no V-toothpick, so a(0) = 0.

At stage 1 we place a V-toothpick upside down, so a(1) = 1.

At every stage the V-toothpicks of the new generation must be connected to the structure by touching with their middle vertex the free ends of the V-toothpicks of the previous generation following a special rule:

The new V-toothpicks must be placed between the imaginary straight line containing the two extreme ends of the V-toothpick of the previous generation and the imaginary straight line that contains the middle vertex of that V-toothpick and that it is parallel to the aforementioned straight line.

A355311(n) gives the number of V-toothpicks added to the structure at the n-th stage.

2*a(n) is the total number of toothpicks of length 1 in the structure after n-th stage.

This cellular automaton is a companion of the Y-toothpick cellular automaton of A160120 in the sense that both essentially grow as an equilateral triangle.

This cellular automaton is slightly less symmetrical than Y-toothpick cellular automaton because its structure has a "backbone" formed by concave hexagons from the center of the triangle to one of its vertices.

The behavior could be very close to A160120 and similar to A153006 (see the graph).

After 18 stages we can see in the structure the following polygons:

- Equilateral triangles of perimeter 3.

- Equilateral triangles of perimeter 6 that contain 4 triangular cells.

- Concave hexagons of perimeter 8 that contain 6 triangular cells.

- Concave dodecagons (or concave 12-gons) of perimeter 18 that contain 22 triangular cells.

Inspired by Neil Sloane's presentation at Rutgers' Experimental Mathematics Seminar (see the Links section).

Beneath the familiar image of every cellular automaton lies an infinite world of hidden patterns, stained-glass windows, gaskets, curves and fractals.

As an example of this statement we will focus on the "toothpick" cellular automata. In general after 2^k stages, k >= 2, these structures looks like the framework of a stained-glass window (without the colored glass). Toothpicks represent the cames of the structure. Now the idea is to put the stained glass.

Here we will use the "toothpick" cellular automaton of A139250.

After every stage the square cells of the newly formed regions will be colored.

We have two colors. If n is odd, they are painted with the color 1. If n is even, they are painted with the color 2.

Note that there are infinitely many rules for coloring a cellular automaton since there are infinitely many colors related to infinitely many sequences, however, the rule used here seems quite natural, since the number of colors coincides with the number of letters of the "word" of this cellular automaton, which is "ab". So here we have toothpicks on the two axes of the infinite square grid, two associated sounds (tick-tock) and two colors.

After 2^k stages, k >= 2, a rectangular-stained-glass window with two colors will have been formed.

Conjecture 1: after 2^k stages the number of cells of color 1 is equal to the number of cells of color 2.

Conjecture 2: after 2^k stages, k >= 2, in the structure there are essentially one major region of color 1 and two major regions of color 2.

It appears that there are certain sub-quadrants that have the complementary structure and the opposite colors of other sub-quadrants.

This sequence is a square array read by antidiagonals upwards that represents the colors (1 or 2) of every cell in the fourth quadrant of the stained-glass windows. The corner of the array represents the cell whose upper-left vertex is the point (0,0) of the fourth quadrant of the structure.

For a binary sequence the 2's should be replaced with 0's.

Note that for the toothpick cellular automaton on triangular grid of A296510 (whose word is "abc") three colors should be used there. Same for the C.A. of A299476 and of A299478.

For more information on the "word" of a cellular automaton see A296612 and see ALSO the third triangle in the example section of A139251.

The following three steps refer to the visualization of hidden gaskets and hidden curves from the stained-glass windows of the toothpick structures.

First, a growth limit is set until the final stage 2^k.

Then the line segments other than the border between the two colors are removed.

Finally the colors are also removed.

In this case, two curves will be formed. One curve on the first and second quadrant and the other curve on the third and fourth quadrant. One curve is the reflection of the other.

After studying and analyzing the curve, a sequence and an animation could be made to represent it, from the stage 1 to n.

The curve obtained resembles the Hilbert curve and the Moore curve, but apparently here the curve is a bit more complex (see the example).