The Game of Life

I've mentioned the mathematician John Conway in three posts to this blog. The first was the Look and Say Sequence on February 10th 2017, the second was the RATS Sequence on September 26th 2020 and the third was the Free Fibonacci Sequences on July 18th 2021.

John Conway: 1937 - 2020
MacTutor Biography

I've known about his Game of Life for quite some time now but had avoided delving into it. However, yesterday I downloaded an iOS app that allows one to play around with it and this kindled an interest to find out more. Here is some information about the game together with its rules taken from Wikipedia:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies, as if by underpopulation.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

Figures 1, 2 and 3 show examples of commonly occurring patterns that occur during the game:

Figure 1: Loaf
Example of a still life

Figure 2: Blinker
Example of an Oscillator

Figure 3: Glider
Example of a Spaceship

The Pulsar is the most common period-3 oscillator as shown in Figure 4.

Figure 4: Pulsar
The most common
Period-3 oscillator

The Wikipedia comments go on to say:

The pulsar is the most common period-3 oscillator. The great majority of naturally occurring oscillators have a period of 2, like the blinker and the toad, but oscillators of all periods are known to exist, and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions. Patterns which evolve for long periods before stabilizing are called Methuselahs, the first-discovered of which was the R-pentomino. Diehard is a pattern that eventually disappears, rather than stabilizing, after 130 generations, which is conjectured to be maximal for starting patterns with seven or fewer cells. Acorn takes 5,206 generations to generate 633 cells, including 13 escaped gliders.

Figure 5: R-Pentomino
The first discovered Methuselah

Of course, I've encountered numerous references to the Game of Life in the OEIS over the years but have uniformly ignored them. OEIS A019473 is one example.

A019473

Number of stable \(n\)-celled patterns ("still lifes") in Conway's Game of Life, up to rotation and reflection.

The initial members of the sequence are: 0, 0, 0, 2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, 3286, 7773, 19044, 45759, 112243 (beginning with \(n\)=1).

Figure 1 shows the Loaf, one of the four 7-celled stable patterns. OEIS A089520 is another such sequence:

A089520

In Conway's Game of Life, the number of steps it takes for an \(n \times n\) square, in which all the cells are in the "on" state, to die out or start to cycle, or -1 if there is no cycle.

The initial members are:

1, 0, 5, 4, 11, 5, 5, 6, 16, 17, 32, 9, 18, 9, 22, 11, 33, 17, 20, 12, 26, 13, 48, 15, 46, 26, 295, 45, 154, 38, 62, 309, 38, 87, 78, 53, 96, 150, 641, 69, 82, 265, 216, 70, 70, 70, 120, 401, 107, 78, 70, 351, 318, 109, 297, 95, 122, -1, -1, 85, 232, 294, 127 (beginning with \(n\)=1).

The 1 x 1 square disappears in one step but the 2 x 2 square (called the Block) is stable and an example of a still life. The 3 x 3 square takes five steps to turn into four blinkers (one of which is shown in Figure 2). The 4 x 4 square takes four steps to disappear and so on. The OEIS comments for this sequence state that:

The -1 terms for \(n\) = 58, 59, 80, 92, 95, 96, 98, 99, 100 correspond to starting \(n \times n \) squares that produce 8 gliders (16 for \(n\) = 99) that go off to infinity, hence never reaching a cycle.

Here is a link to an interesting article in Quanta Magazine about the latest news regarding the Game of Life. Here is an excerpt:

Throughout the 1970s, mathematicians and hobbyists filled in the other short periods and found a smattering of longer ones. Eventually, mathematicians discovered a systematic way to build long-period oscillators. But oscillators with periods between 15 and 43 proved tough to find. “People have been trying to figure out the middle for years,” said Maia Karpovich, a graduate student at the University of Maryland. Filling in the gaps forced researchers to dream up a slew of new techniques that pushed the boundaries of what was thought possible with cellular automata, as mathematicians call evolving grids like Life.

Now Karpovich and six co-authors have announced in a December preprint that they have found the last two missing periods: 19 and 41. With those gaps filled, Life is now known to be “omniperiodic” — name a positive integer, and there exists a pattern that repeats itself after that many steps.

Periods of Prime Reciprocals

I've written about the periodic decimal representations of prime number reciprocals before, specifically in a post titled Cyclic Numbers on November 23rd 2019. All prime reciprocals are periodic with periods that are of the form:$$ \frac{p-1}{k} \text{ where } k=1, 2, 3, \dots $$What I'd never considered however, was the relative frequencies of these periods for different values of \(k\). It's not difficult to generate a table (permalink) to show this information. I've considered only primes in the range up to 40,000. See Figure 1.

Figure 1

As can be seen, more than a third of primes have reciprocal periods where \(k=1\). It's only when we reach \(k=31\) that we find no such primes in the range up to 40000. However, if we extend the range up to one million then there are 24 primes \(p\) with a period of \( (p-1)/31 \). These primes are (permalink):

49663, 113647, 129023, 136897, 160829, 163061, 381487, 437287, 462149, 501829, 503131, 591233, 675553, 697687, 699299, 701593, 770909, 791927, 800731, 860623, 863909, 918779, 933349, 969743

It would seem that for any arbitrary \(k\) there will be an infinite series of prime numbers \(p\) have a reciprocal period of \( (p-1)/k \). Sometimes the initial prime number is not all that large. Take \(k=101\) for example. In the range up to one million there are two primes with this property, namely 5051 and 637513. For \( k=197 \) there are three primes: 74861, 818339 and 931811.

For any composite number, the period of its reciprocal is the product of the periods of its prime factors divided by their greatest common divisor. For example:$$ \begin{align} 2077 &= 31 \times 67\\ \text{period} \Big ( \frac{1}{31} \Big ) &= 15 \\ \text{period}  \Big (\frac{1}{67} \Big )&= 33 \\ \text{gcd} (15,33) &=3 \\ \text{period} \Big ( \frac{1}{2077} \Big ) &= \frac{15 \times 33}{3} \\ &= \frac{495}{3} \\ &=165 \end{align}$$What's also of interest is a list of the first primes that are divisible by the various divisors once 1 is subtracted from them. The results are shown in Figure 2 over the range up to 100,000. Notice that there is no result for 41 in this range. Notice that for 2 and 5 a result of 1 is returned. This is because when \(n\) is composite, \(n\).period() returns the value 1 (permalink).

Figure 2

The first prime less 1 that is divisible by 41 is 118901 whose reciprocal has a period of 2900. Thus 41 holds the record for hosting the largest prime minus 1 divisible by numbers between 1 and 50.

Periodic Unitary Aliquot Sequences.

At first glance, the phrase "periodic unitary aliquot sequences" can sound intimidating so it needs to be broken down into its individual components. Let's start with a definition of aliquot taken from study.com:

An aliquot is a portion or part of a larger whole. An aliquot, or the aliquot part as it is referred to in mathematics, is defined as a positive proper divisor of a number. A divisor refers to a whole number that can be divided evenly into a number.

Using the number associated with my diurnal age today, 27208, the aliquot parts of this number are 1, 2, 4, 8, 19, 38, 76, 152, 179, 358, 716, 1432, 3401, 6802 and 13604. 

The next term to deal with is unitary. The unitary divisors of a number are defined by Wikipedia as follows:

\(a\) is a unitary divisor (or Hall divisor) of a number \(b\) if \(a\) is a divisor of \(b\) and if \(a\) and \(b/a\) are coprime, having no common factor other than 1. Thus, 5 is a unitary divisor of 60, because 5 and 60/5 =12 have only 1 as a common factor, while 6 is a divisor but not a unitary divisor of 60, as 6 and 60/6 = 10 have a common factor other than 1, namely 2. 1 is a unitary divisor of every natural number. 

In the case of 27208, the unitary divisors are 1, 8, 19, 152, 179, 1432, 3401, 27208 but the unitary aliquot divisors are 1, 8, 19, 152, 179, 1432, 3401. See my blog post Unitary Divisors.

Next we need to tackle aliquot sequences. Here is a definition:

Now in the case of 27208, the aliquot sequence terminates in zero. Here is the trajectory (permalink):

27208, 26792, 26668, 21212, 15916, 13316, 9994, 5846, 3274, 1640, 2140, 2396, 1804, 1724, 1300, 1738, 1142, 574, 434, 334, 170, 154, 134, 70, 74, 40, 50, 43, 1, 0

This sequence is terminating and not periodic. However, a unitary aliquot sequence uses the unitary divisors and can behave quite differently. In the case of 27208, the sequence becomes periodic with the following trajectory (permalink):

27208, 5192, 1288, 440, 208, 30, 42, 54, 30

27208 is a member of OEIS A003062:

A003062

Beginnings of periodic unitary aliquot sequences.

The initial members are:

6, 30, 42, 54, 60, 66, 78, 90, 100, 102, 114, 126, 140, 148, 194, 196, 208, 220, 238, 244, 252, 274, 288, 292, 300, 336, 348, 350, 364, 374, 380, 382, 386, 388, 400, 420, 436, 440, 476, 482, 484, 492, 516, 528, 540, 542, 550, 570, 578, 592, 600, 612, 648, 660, 680, 688, 694, 708, 720, 722, 740, 756, 758, 764, 766, 770, 780, 784, 792, 794, 812

Thus periodicity is fairly common for these types of sequences, quite unlike the aliquot sequences which nearly all end in 0. See my post Aliquot Sequences.

The RATS Sequence Revisited

It was on Saturday, 26th September 2020, that I first wrote about the RATS sequence, the acronym standing for Reverse --> Add --> Then Sort. On that occasion I was looking at the number 26109 that is a member of OEIS A114613:

A114613

Starting numbers for which the RATS sequence has eventual period 3.

Yesterday the number associated with my diurnal age, 27099, is the next member of that sequence. The sequence runs (permalink):

20169, 20709, 21159, 22149, 23139, 24129, 25119, 26109, 27099, 28089, 29079, 30159, 30168, 30708, 30789, 31149, 31158, 31779, 32139, 32148, 32769, 33129, 33138, 33759, 34119, 34128, 34749, 35109, 35118, 35739, 36108, 36729, 37098, 37719, 38088, 38709, 39078, 39699, ...

As can be seen, the members of this sequence are few and far between. Up to 40,000, there are only 38 terms. In the case of 27099 the progression is:

27099, 111267, 337788, 1122255, 4446666, 1111113, 2222244, 4446666

There are sequences with different periods but for most numbers the progression is infinite. See Table 1:

Table 1

The original post contains more information that I won't repeat here. Using my diurnal age today (27100) as an example, we see the divergent period-2 pattern emerging, with the red showing the progression of this period-2 pattern (permalink).

27100
22277
49999
134999
113344
555566
1111222
2333333
5566666
11222333
44444455
88889999
178888888
156777779
113344555
666677888
1444555555
167999
116677
238889
1122277
4448888
12333337
55666688
133333444
556667777
1233334444
5566667777

12333334444

55666667777

123333334444

556666667777

1233333334444

5566666667777

12333333334444

55666666667777

123333333334444

556666666667777

1233333333334444

5566666666667777

It won't be until I turn 28089 days old that I'll meet this sequence again. The Wolfram Demonstration Project also features the RATS sequence and displays the progression of terms up till the start of the period-2 pattern. See Table 2.

Table 2

Continued Fractions of Square Roots

It's all too easy, using online resources like WolframAlpha or SageMathCell, to extract a variety of information about continued fractions. For example, today I turned \(26195\) days old and this number is a member of OEIS A042431:

A042431

Denominators of continued fraction convergents to \( \sqrt{743} \).

To confirm that \(26195\) is indeed a member of this sequence, I would normally use SageMathCell but others would turn to WolframAlpha and, using the latter, it can be seen in Figure 1 that \(26195\) is indeed a denominator in one of the convergent fractions, specifically:$$ \displaystyle \frac{714024}{26195}$$

Figure 1

It's easy to take for granted that the continued fraction of an irrational number that is a square root (like \( \sqrt{743} \)) is always periodic. A good explanation of why this is so can be found on this site. In the following, I'm reproducing the site's conversion of \( \sqrt{5} \) to a continued fraction (and practising my LaTeX at the same time).

$$\begin{aligned}
\sqrt{5}&=2+x\\
5&=(2+x)^2 \\
&=4+4x+x^2\\
&=4+x\,(4+x)\\
5-4&=x\,(4+x)\\
1&=x\,(4+x)\\
x&=\frac{1}{4+x}\\
\text{ Thus } \sqrt{5}&=2+\frac{1}{4+x}\\
&=2+\frac{1}{4+\displaystyle \frac{1}{4+x}}\\
&=2+\frac{1}{4+\displaystyle \frac{1}{4+\displaystyle \frac{1}{4+x}}} \text{ etc.}\\
\end{aligned}$$Clearly, we can write \( \sqrt{5}=[2;\overline 4]\) where the overline represents repetition. In the case of \( \sqrt{743}\), we have \([27;\overline{3,1,7,27,7, 1, 3, 54}]\). The site referred to earlier goes on to develop a general algorithm for determining the periodic continued fraction of any irrational square root. The table at the end of this post lists the continued fractions of the square roots of the first 99 natural numbers (even those that aren't irrational). 

√n [ a; Period ] √1 [ 1; ] √2 [ 1; 2 ] √3 [ 1; 1, 2 ] √4 [ 2; ] √5 [ 2; 4 ] √6 [ 2; 2, 4 ] √7 [ 2; 1, 1, 1, 4 ] √8 [ 2; 1, 4 ] √9 [ 3; ] √10 [ 3; 6 ] √11 [ 3; 3, 6 ] √12 [ 3; 2, 6 ] √13 [ 3; 1, 1, 1, 1, 6 ] √14 [ 3; 1, 2, 1, 6 ] √15 [ 3; 1, 6 ] √16 [ 4; ] √17 [ 4; 8 ] √18 [ 4; 4, 8 ] √19 [ 4; 2, 1, 3, 1, 2, 8 ] √20 [ 4; 2, 8 ] √21 [ 4; 1, 1, 2, 1, 1, 8 ] √22 [ 4; 1, 2, 4, 2, 1, 8 ] √23 [ 4; 1, 3, 1, 8 ] √24 [ 4; 1, 8 ] √25 [ 5; ] √26 [ 5; 10 ] √27 [ 5; 5, 10 ] √28 [ 5; 3, 2, 3, 10 ] √29 [ 5; 2, 1, 1, 2, 10 ] √30 [ 5; 2, 10 ] √31 [ 5; 1, 1, 3, 5, 3, 1, 1, 10 ] √32 [ 5; 1, 1, 1, 10 ] √33 [ 5; 1, 2, 1, 10 ] √34 [ 5; 1, 4, 1, 10 ] √35 [ 5; 1, 10 ] √36 [ 6; ] √37 [ 6; 12 ] √38 [ 6; 6, 12 ] √39 [ 6; 4, 12 ] √40 [ 6; 3, 12 ] √41 [ 6; 2, 2, 12 ] √42 [ 6; 2, 12 ] √43 [ 6; 1, 1, 3, 1, 5, 1, 3, 1, 1, 12 ] √44 [ 6; 1, 1, 1, 2, 1, 1, 1, 12 ] √45 [ 6; 1, 2, 2, 2, 1, 12 ] √46 [ 6; 1, 3, 1, 1, 2, 6, 2, 1, 1, 3, 1, 12 ] √47 [ 6; 1, 5, 1, 12 ] √48 [ 6; 1, 12 ] √49 [ 7; ] √50 [ 7; 14 ]

√n [ a; Period ] √51 [ 7; 7, 14 ] √52 [ 7; 4, 1, 2, 1, 4, 14 ] √53 [ 7; 3, 1, 1, 3, 14 ] √54 [ 7; 2, 1, 6, 1, 2, 14 ] √55 [ 7; 2, 2, 2, 14 ] √56 [ 7; 2, 14 ] √57 [ 7; 1, 1, 4, 1, 1, 14 ] √58 [ 7; 1, 1, 1, 1, 1, 1, 14 ] √59 [ 7; 1, 2, 7, 2, 1, 14 ] √60 [ 7; 1, 2, 1, 14 ] √61 [ 7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14 ] √62 [ 7; 1, 6, 1, 14 ] √63 [ 7; 1, 14 ] √64 [ 8; ] √65 [ 8; 16 ] √66 [ 8; 8, 16 ] √67 [ 8; 5, 2, 1, 1, 7, 1, 1, 2, 5, 16 ] √68 [ 8; 4, 16 ] √69 [ 8; 3, 3, 1, 4, 1, 3, 3, 16 ] √70 [ 8; 2, 1, 2, 1, 2, 16 ] √71 [ 8; 2, 2, 1, 7, 1, 2, 2, 16 ] √72 [ 8; 2, 16 ] √73 [ 8; 1, 1, 5, 5, 1, 1, 16 ] √74 [ 8; 1, 1, 1, 1, 16 ] √75 [ 8; 1, 1, 1, 16 ] √76 [ 8; 1, 2, 1, 1, 5, 4, 5, 1, 1, 2, 1, 16 ] √77 [ 8; 1, 3, 2, 3, 1, 16 ] √78 [ 8; 1, 4, 1, 16 ] √79 [ 8; 1, 7, 1, 16 ] √80 [ 8; 1, 16 ] √81 [ 9; ] √82 [ 9; 18 ] √83 [ 9; 9, 18 ] √84 [ 9; 6, 18 ] √85 [ 9; 4, 1, 1, 4, 18 ] √86 [ 9; 3, 1, 1, 1, 8, 1, 1, 1, 3, 18 ] √87 [ 9; 3, 18 ] √88 [ 9; 2, 1, 1, 1, 2, 18 ] √89 [ 9; 2, 3, 3, 2, 18 ] √90 [ 9; 2, 18 ] √91 [ 9; 1, 1, 5, 1, 5, 1, 1, 18 ] √92 [ 9; 1, 1, 2, 4, 2, 1, 1, 18 ] √93 [ 9; 1, 1, 1, 4, 6, 4, 1, 1, 1, 18 ] √94 [ 9; 1, 2, 3, 1, 1, 5, 1, 8, 1, 5, 1, 1, 3, 2, 1, 18 ] √95 [ 9; 1, 2, 1, 18 ] √96 [ 9; 1, 3, 1, 18 ] √97 [ 9; 1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18 ] √98 [ 9; 1, 8, 1, 18 ] √99 [ 9; 1, 18 ]