The inventor of the Game of Life, John H. Conway, passed away last week, due to the novel coronavirus. Maybe he would have preferred to die of something boring, like the heart attack that claimed Erdős Pál’s life.
Though a really interesting death, like Évariste Galois’s in a duel, would not have been one for Conway, a very friendly and generous spirit. Neil Sloane remembered how quickly Conway would respond to his topic suggestions.
Of course Sloane is a very prominent mathematician in his own right. But Conway also had time for his students at Princeton University, students at other universities, and even for random dilettantes.
Maybe I should have reached out to him on an algebraic number theory question I’m stuck on. He wasn’t particularly known for algebraic number theory, but his interests ran almost as wide as Erdős’s.
Erdős was the Kevin Bacon of mathematics. Since Conway collaborated with Erdős on a paper on the distribution of values of angles determined by coplanar points for the Journal of the London Mathematical Society, Conway has Erdős number 1.
Since Erdős died in 1996, there are now less than 500 mathematicians with Erdős number 1, and Conway’s death drops that number further down. Sloane is at two degrees of separation from Erdős in at least two ways, one of those ways being through Conway.
The Game of Life was one of Conway’s earliest accomplishments. Like Beethoven with his Septet in E-flat major, Opus 20, Conway got a little sick and tired of being asked about the Game of Life.
The simple rules of the game quickly lead to unexpected patterns for almost any initial state. It’s quite mesmerizing. The BitStorm implementation of the Game of Life is fairly intuitive. You can choose from the presets, add cells, step through one generation at a time, and intervene as often or as seldom as you like.
For these illustrations, I started with the Gosper glider gun (a preset) and added a few static groups, oscillators and groups that have somewhat longer cycles.
One step after that:
Then another step:
Skipping ahead to step 74:
The Gosper glider gun has been disrupted. But it still generates plenty of interesting activity. Here it is at step 216:
Step 885:
Step 1,003:
Step 1,098:
By Step 1,340, the system has settled on a dull monotony of static blocks and oscillators.
So I intervene to throw in a “spaceship” to try to break up some of the blocks and oscillators.
Doesn’t look like much, but it’ll do more than some more intensive interventions I could have tried. Here it is seventy steps after the intervention:
Then 329 steps after:
And 730 steps after:
At 800 steps after the intervention, it’s back to the monotony of blocks and oscillators.
The Game of Life is not the only thing Conway can or should be remembered for. His collaboration with Neil Sloane on the book Sphere Packings, Lattices and Groups (published by Springer-Verlag) was a landmark publication on the topic.
Another Conway creation that might have eventually annoyed Conway if it had been better known is PrimeGame, a program for his FRACTRAN, a Turing-complete computer. PrimeGame is, in my opinion, a wonderful Rube Goldberg machine.
The ideal prime number listing function is concise, elegant and efficient. In Scala (a programming language for the Java Virtual Machine), the prime listing function is often implemented to use what’s called “lazy” evaluation.
The following is something I found on the Internet and adapted according to deprecation warnings in InteilliJ IDEA and the local Scala REPL.
val prime: LazyList[Int] = 2 #:: LazyList.from(3).filter(i => prime.takeWhile {
j => j * j <= i
}.forall {
k => i % k != 0
})
Here’s a Scastie snippet to demonstrate the prime listing function used to find primes of the form 6k + 1 less than 1000.
To implement PrimeGame in Scala we’ll need to do a lot more. First, we’ll need the fractions 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 1/17, 11/13, 13/11, 15/2, 1/7, 55. Does the Scala SDK have something to represent fractions? I’m not sure, but I’ve got my own that I can use.
We start with 2, try multiplying it by each of the listed fractions one by one until we find one that gives an integer: 34/91 is not an integer, 156/85 is not an integer either, neither is 38/51, and so on and so forth until we find that 2 × 15/2 = 15.
We repeat the process with 15: 255/91 is not an integer, 234/17 is not an integer either, and so on and so forth until we get to 15 × 55 = 825.
This leads to the sequence 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4. Noting that 4 is a power of 2, we see that 4 = 22. And this tells us that 2 is prime, which we already knew.
We put 4 back into the “machine” and obtain the sequence 4, 30, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620, 4060, 10780, 12740, 2380, 2184, 408, 152, …, 8. Noting that 8 is a power of 2, we see that 8 = 23, telling us that 3 is prime, something we also already knew.
These sequences really are one long, infinite sequence. Eight thousand terms are listed in Sloane’s Online Encyclopedia of Integer Sequences, entry A7542.
Looking at the “B-file” for A7542 (click the “Alois P. Heinz, Table of n, a(n) for n=1..8103” link from the entry’s main page), we see that 4 occurs at position 20, 8 occurs at position 70, 32 occurs at position 282, 128 occurs at position 711, etc.
It turns out the B-file, long as it is, is only good to obtain the first seven primes. With our modern computers, we could nevertheless obtain more terms fairly quickly.
In this way, we’ll slowly but surely obtain 25, 27, 211, 213, 217, 219, etc. My Scala fraction implementation uses 64-bit integers. I think I’d run into trouble long before (no pun intended) getting to 267.
Scala makes it quite simple to change that to “big” integers (integers of arbitrary bit width, limited only by the resources available to the Java Virtual Machine). I’m going to hold off on that, though, I’m running into a lot of problems and rabbit holes trying to understand lazy collections, and thinking that maybe I’m using the wrong collection.
Then I decided it would be better to try to simplify to something more procedural and that that would be good enough for this post. But then my Scala program turned out to be way too long to put into a Scastie snippet.
And even if I got that to work, it would still not give the proper impression of what a cool Rube Goldberg machine Conway’s PrimeGame is. So I finally decided to just use an illustration I made eight years ago:
Rest in peace, John Conway.