Blog > The Q-Toothpick Cellular Automaton

## The Q-Toothpick Cellular Automaton

March 26th, 2011

The Q-toothpick cellular automaton (defined earlier this month by Omar E. Pol) is described by the following simple rules:

1. On an infinite square grid, draw a quarter circle from one corner of a square to the opposite corner of that square:
2. Call an endpoint of a quarter circle (or a “Q-toothpick”) exposed if it does not touch the endpoint of any other quarter circle.
3. From each exposed endpoint, draw two more quarter circles, each of the same size as the first quarter circle you drew. Furthermore, the two quarter circles that you draw are the ones that can be drawn “smoothly” (without creating a 90° or 180° corner). Thus the next two generations of the automaton are (already-placed quarter circles are green, newly-added quarter circles are red):

The name “Q-toothpick” comes from its analogy to the more well-studied toothpick automaton (see Sloane’s A139250 and this paper), in which toothpicks (rather than quarter circles) are repeatedly placed on a grid where exposed ends of other toothpicks lie. In this post, we will examine how this automaton evolves over time, and in particular we will investigate the types of shapes that it produces.

### Counting Q-Toothpicks

While the Q-toothpick automaton appears quite random and unpredictable for the first few generations, evolving past generation 6 or so reveals several patterns. The following image depicts the evolution of the automaton for its first 19 generations.

The first 19 generations of the Q-toothpick cellular automaton (red segments are pieces that are newly added in the current generation)

Perhaps the most notable pattern is that the grid is more or less filled up in an expanding square starting from the initial Q-toothpick. In fact, by inspecting generations 4, 6, 10, 18, we see that at generation 2n + 2 (n = 1, 2, 3, …) the automaton has roughly filled in a square of side length 2n+1 + 1, and then evolution continues from there on out of the corners of that square. Also, the number of cells added (A187211) at these generations can now easily be computed:

A187211(2n + 2) = 16 + 8(2n-1 – 1) for n ≥ 3.

Furthermore, the growth in the following generations repeats itself. In particular, we have:

A187211(2n + 3) = 22 for n ≥ 1,
A187211(2n + 4) = 40 for n ≥ 2,
A187211(2n + 5) = 54 for n ≥ 2.

Similarly, for n ≥ 3, the four values of A187211(2n + 6) through A187211(2n + 9) are similarly constant (their values are 56, 70, 120, and 134). In general, for n ≥ k the 2k-1 values of A187211(2n + 2k-1 + 2) through A187211(2n + 2k + 1) are constant in n, though I am not aware of a general formula for what these constants are. If we ignore the first four generations and arrange the number of Q-toothpicks added in each generation in rows of length 2n, we obtain a table that begins as follows:

22, 20
22, 40, 54, 40
22, 40, 54, 56, 70, 120, 134, 72
22, 40, 54, 56, 70, 120, 134, 88, 70, 120, 150, 168, 246, 360, 326, 136

C scripts are provided at the end of this post for computing the values of A187210 and A187211 (and hence the values in the above table).

### Shapes Traced Out by Q-Toothpicks

In the graphic above that depicts the initial 19 generations of the Q-toothpick automaton, several shapes are traced out, including circles, diamonds, hearts, and several nameless blobs:

By far the most common of these shapes are circles, diamonds and hearts. The fourth shape appears only on the diagonal and it’s not difficult to see that it forever will make up the entirety of the diagonal (with the exception of the circle in the center). The fifth and sixth objects are the first two members of an infinite family of objects that appear as the automaton evolves. The fifth object first appears in generation 9, and sixth object (which is basically two copies of the fifth object) first appears in generation 17. The following object, which is basically made up of two copies of the sixth object (i.e., four copies of the fifth object) first appears in generation 33:

In general, a new object of this type (made of 2n copies of the fifth object above) first appears in generation 2n+3 + 1. In fact, these objects are the only ones that are traced out by this automaton. [Edit: this final claim is not true! See ebcube’s great post that shows a double-heart shape in generation 31.]

Update [March 28, 2011]: I have added a script that counts the number of circles, diamonds, and hearts in the nth generation of the Q-toothpick automaton, and another script that computes Sloane’s A187212.

• A187210.c – computes the total number of Q-toothpicks present in the nth generation
• A187211.c – computes the number of Q-toothpicks added in the nth generation
• A187212.c – computes the number of Q-toothpicks if we restrict them to the positive quadrant
• count_shapes.c – computes the number of circles, diamonds, and hearts in the nth generation
1. May 24th, 2011 at 22:50 | #1

A ruletable-like version (it should be right, but I haven’t tested it)

0 is void
1 is a line from bottom-left to top-right via top-left
2 is a line from top-left to bottom-right via top-right (= 1 rotated 90º)
3 is a line from top-right to bottom-left via bottom-right (= 1 rotated 180º)
4 is a line from bottom-right to top-left via bottom-left (= 1 rotated 270º)
x is any value, including 0

0010xxxxx3
0xx020xxx4
0xxxx030x1
00xxxxx042

0xxxx010x3
00xxxxx024
0030xxxxx1
0xx040xxx2

00xxxxx102
0200xxxxx3
0xx300xxx4
0xxxx400x1

01xxxxx004
0002xxxxx1
0xx003xxx2
0xxxx004x3

2. October 15th, 2011 at 18:37 | #2

Hello Nathaniel. The fourth shape looks like a flower vase.

3. September 28th, 2012 at 19:06 | #3

It appears that the number of hearts present in the n-th generation (Sloane’s A188346) equals the number of rectangles of area = 2 present in the (n – 2)nd generation of the toothpick structure of Sloane’s A139250, assuming the toothpicks have length 2, if n >= 3.

1. No trackbacks yet.