## The Q-Toothpick Cellular Automaton

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

- On an infinite square grid, draw a quarter circle from one corner of a square to the opposite corner of that square:
- Call an endpoint of a quarter circle (or a “Q-toothpick”)
*exposed*if it does not touch the endpoint of any other quarter circle. - 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.

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 2^{n} + 2 (n = 1, 2, 3, …) the automaton has roughly filled in a square of side length 2^{n+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(2^{n} + 2) = 16 + 8(2^{n-1} – 1) for n ≥ 3.

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

A187211(2^{n} + 3) = 22 for n ≥ 1,

A187211(2^{n} + 4) = 40 for n ≥ 2,

A187211(2^{n} + 5) = 54 for n ≥ 2.

Similarly, for n ≥ 3, the four values of A187211(2^{n} + 6) through A187211(2^{n} + 9) are similarly constant (their values are 56, 70, 120, and 134). In general, for n ≥ k the 2^{k-1} values of A187211(2^{n} + 2^{k-1} + 2) through A187211(2^{n} + 2^{k} + 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 2^{n}, 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

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 2^{n} copies of the fifth object above) first appears in generation 2^{n+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.

**Download:**

- 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

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

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

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.