1-Cell Thick Patterns (1)

Recently, I have programmed a script in Perl for Golly. It explores all possible patterns of height 1. The method is the exhaustive enumeration of sequences that don’t contain any isolated live cells or pairs of live cells.

This task has been done before by Paul Callahan in October 1998, when he did an exhaustive search to find the smallest undimensional example which exhibits infinite growth (that is, the population tends to infinity, or at least is unbounded). However, it seems that the only result he reported to a private mailing list of Life enthusiasts was the one that he was searching for: a 39×1 pattern that produces two block-laying switch engines.

I ignore how much time Callahan needed to generate such a discovery, but with today’s computers, we can accomplish this feat in less than two days. (Assume a well-designed script that also ignores patterns with only a mix of 3 and/or 4-cell groups; note that removing symmetrical patterns also helps to improve the overall speed.)

The purpose here is to comment on the patterns that my script found in terms of their increasing final population.

7-bit patterns

The first and only pattern that verifies the restrictions above is the following:

Pattern (RLE)
#CXRLE Pos=0,0
x = 7, y = 1, rule = B3/S23
7o!

It runs for 14 generations and produces the following:

Four beehives. Final population: 24 cells.

8-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 8, y = 1, rule = B3/S23
8o!

It runs for 48 generations and produces this:

Final population: 40 cells.

9 and 10-bit patterns

Adding 1 or 2 bits does not produce patterns with higher nor equal final population with respect to the 8-bit case.

11-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 11, y = 1, rule = B3/S23
7ob3o!

It runs for 185 generations and produces the following:

Curiously enough, the initially asymmetrical pattern becomes symmetrical (this happens at generation 24).

“Patterns with no initial symmetry tend to become symmetrical. Once this happens the symmetry cannot be lost, although it may increase in richness.”
Martin Gardner, The fantastic combinations of John Conway’s new solitaire game “life”
Scientific American 223 (October 1970): 120-123.

Final population: 104 cells.

12, 13, and 14-bit patterns

Again, adding up to 3 bits does not produce patterns with higher nor equal final population with respect to the 11-bit case.

15-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 15, y = 1, rule = B3/S23
5ob3o2b4o!

Note that 15-bit does not mean 15-cell (live cells and dead cells are bits). It runs for 3183 generations and produces this:

It reminds me of a bat. Final population: 1059 cells (including six gliders).

16, 17, and 18-bit patterns

Again, adding up to 3 bits does not produce patterns with higher nor with equal final population with respect to the 15-bit case.

19-bit patterns

The only interesting pattern is:

Pattern (RLE)
#CXRLE Pos=0,0
x = 19, y = 1, rule = B3/S23
5ob3o2b4ob3o!

After 37 generations this 17-bit pattern becomes something identical to the above-mentioned 15-bit pattern after 37 generations also. The number of interesting generations and final population are thus the same in both cases. Note that both patterns are similar except for the additional blinker.

20 and 21-bit patterns

No patterns with higher/equal final population with respect to the 19-bit case.

22-bit patterns

The only interesting pattern is:

Pattern (RLE)
#CXRLE Pos=0,0
x = 22, y = 1, rule = B3/S23
5ob3o2b4o4b3o!

After 118 generations this 22-bit pattern becomes identical to the above-mentioned 15-bit pattern after 118 generations also. The number generations and final population are the same in both cases. Note that again, both patterns are similar except for the additional blinker.

23-bit patterns

The only interesting pattern is:

Pattern (RLE)
#CXRLE Pos=0,0
x = 23, y = 1, rule = B3/S23
5ob3o3b3o2b6o!

After 13 generations this 23-bit pattern becomes equal to the above-mentioned 15-bit pattern after 13 generations also. Same number of generations and final population ensues. Note that again, both patterns are similar except for 3-cell & 5-cell combination that in the long term behaves identically to a 4-cell.

This is the last occurrence of a relative of that 15-bit pattern relative.

24-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 24, y = 1, rule = B3/S23
5o2b4o2b3o5b3o!

It runs for 5029 generations and produces the following:

Final population: 1206 cells (including twenty-two gliders).

25-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 25, y = 1, rule = B3/S23
8o3b4o2b3o2b3o!

It runs for 5685 generations and produces the following:

Final population: 1804 cells (including again twenty-two gliders).

26 and 27-bit patterns

No patterns with higher/equal final population with respect to the 25-bit case.

28-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 28, y = 1, rule = B3/S23
3ob5ob3o2b8o2b3o!

It runs for 5909 generations and produces this:

Final population: 1888 cells (including twenty-four gliders).

29-bit patterns

No patterns with higher/equal final population with respect to the 28-bit case.

30-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 30, y = 1, rule = B3/S23
4o4b4o3b11ob3o!

It runs for 4770 generations and produces the following:

Final population: 2116 cells (including eighteen gliders).

31 and 32-bit patterns

No patterns with higher/equal final population with respect to the 30-bit case.

33-bit patterns

There are two patterns that produce the same, larger, final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 33, y = 1, rule = B3/S23
3ob5o4b3o2b9o3b3o!

Pattern (RLE)
#CXRLE Pos=0,0
x = 33, y = 1, rule = B3/S23
4ob8o4b4ob5ob5o!

The first one runs for 6387 generations while the second one runs for 6385 generations. After 64 generations the output of the first pattern becomes the same as the output of the second pattern after 62 generations (but shifted to the left by one cell). Both patterns produce the same output:

Final population: 2332 cells (including twenty-four gliders).

34-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 34, y = 1, rule = B3/S23
7ob3ob8ob4ob4ob3o!

It runs for 9362 generations and produces the following:

Final population: 2642 cells (including twenty-six gliders and four spaceships).

35-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 35, y = 1, rule = B3/S23
6ob3ob8o5b5o3b3o!

It runs for 12543 generations and produces the following:

Final population: 3072 cells (including thirty six gliders).

36-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 36, y = 1, rule = B3/S23
8o2b3ob4o2b6o2b3o2b3o!

It runs for 7784 generations and produces the following:

Final population: 3164 cells (including, again, thirty six gliders).

37-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 37, y = 1, rule = B3/S23
5o2b8ob4o3b3ob5o2b3o!

It runs for 9720 generations and produces the following:

Final population: 3384 cells (including, again, thirty six gliders).

38-bit patterns

There is a pattern with larger final population:

Pattern (RLE)
#CXRLE Pos=0,0
x = 38, y = 1, rule = B3/S23
6o2b3o2b5o2b5o3b4o2b4o!

It runs for 14911 generations and produces the following:

Final population: 3554 cells (including, forty four gliders).

39-bit patterns

There is a pattern with larger final population. Of course! It is Callahan’s pattern:

Pattern (RLE)
#CXRLE Pos=0,0
x = 39, y = 1, rule = B3/S23
8ob5o3b3o6b7ob5o!

It runs forever. It produces two block-laying switch engines, and achieves stability at generation 1483:

Final population: infinite (including, two gliders and infinite blocks).

Advertisements

One Response to “1-Cell Thick Patterns (1)”

  1. Oscar Cunningham Says:

    I don’t know if you’re still looking at this site, but recently I’ve become interested in one cell thick patterns as well, and I was wondering if you could send me a copy of your perl script for Golly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: