One of the most interesting patterns that has ever been constructed in Conway’s Game of Life is primer, a gun that fires lightweight spaceships that represent exactly the prime numbers. It was constructed by Dean Hickerson way back in 1991, yet arguably no pattern since then has been constructed that’s as interesting. It seems somewhat counter-intuitive at first that the prime numbers, which seem somehow “random” or “unpredictable”, can be generated by this (relatively simple) pattern in the completely deterministic Game of Life.

Primer, the prime-generating gun

The gun works by firing lightweight spaceships westward, and destroying them via glider guns that emulate the Sieve of Eratosthenes. A lightweight spaceship makes it past the left edge of the gun at generation 120N if and only if N is a prime number (though for technical reasons, 2 and 3 are not outputted).

The first six lightweight spaceships output by primer

It wasn’t too long after making primer that Hickerson realized that he could attach a gun to the bottom-left corner of it to turn it into a twin prime calculator by allowing each lightweight spaceship through only if another lightweight spaceship passed through 240 generations earlier. Similarly, Jason Summers constructed a Fermat prime calculator in 2000 by shooting a glider at the lightweight spaceship stream every generation of the form 120(2^N + 1), which ends up detecting exactly the Fermat primes.

So what other families of primes can we compute in Life by altering the output of the original prime-generating gun?

Mersenne Primes

Mersenne primes can easily be computed using the exact same method as was used in the Fermat prime calculator — use a 7-engine Cordership (in blue below) to bounce a glider back at the stream of lightweight spaceships, with the time required for the glider to reach the stream doubling each time. An inverter (in green below) eliminates all lightweight spaceships that try to get past it unless it just received a glider from the Cordership. By fiddling around with timing a tiny bit, we then have a Mersenne prime calculator:

Mersenne Prime Calculator

• Java link: here
• RLE file: here

Prime Quadruplets

Four prime numbers are said to form a prime quadruplet if they are of the form (p, p+2, p+6, p+8) for some prime number p, which is the closest that four prime numbers can be together (except for the degenerate cases of (2,3,5,7) and (3,5,7,11)). Prime quadruplets are easy to compute because they can be thought of as consecutive pairs of twin primes. Since we already have a twin prime calculator, we can just repeat its reaction.

The twin prime calculator works by attaching a period 240 gun (in green below) to the bottom-left corner of primer. If it is timed correctly, it has the effect of allowing a lightweight spaceship through at generation 240N if and only if a lightweight spaceship tried to pass through at generation 240(N-1). Thus, it will only allow a lightweight spaceship through if it represents a prime number of the form p+2, where p is another prime number. Well, simply attaching a period 720 gun (in blue below) then allows a spaceship through at generation 720N if and only if a lightweight spaceship tried to pass through at generation 720(N-1). This has the effect of allowing a lightweight spaceship to pass through only if it represents a twin prime pair (p,p+2), and there is another twin prime pair of the form (p-6,p-4). That is, the only lightweight spaceships allowed through are those representing the upper members of prime quadruplets.

Prime quadruplet calculator

• Java link: here
• RLE file: here

Prime Pairs of the Form (p, p+2k)

The twin prime calculator mentioned earlier gives a way of computing prime pairs of the form (p,p+2), but what about pairs where the gap is larger than 2? For example, the k=2 case gives what are known as cousin primes, and the k=3 case gives sexy primes (yes, really).

For the case of cousin primes, the thing to notice is that every pair of cousin primes (except for the first pair, (3,7)) must be of the form (6n+1, 6n+5) for some natural number n. Thus, we can use two period 720 guns (in blue below) to allow only the upper prime in a cousin prime pair to pass through. This is achieved by having the top gun fire at the lightweight spaceships representing primes of the form 6n+1 — if a lightweight spaceship is hit, then a block is created in the path of the other gun, which is fired at lightweight spaceships representing primes of the form 6n+5. If a prime was present at 6n+1, then the lightweight spaceship makes it through unharmed at 6n+5. If there was no prime present at 6n+1, then the bottom gun destroys the lightweight spaceship representing 6n+5.

Cousin prime calculator

• Java link: here
• RLE file: here

Extending this idea to prime pairs of the form (p,p+2k) for k ≥ 3 is a bit more challenging, however, because it is possible for pairs to overlap. For example, (37,43) is a sexy prime pair, as is (41,47). Up until now we have only been able to detect single pairs at a time, since the block that acts as our “counter” that keeps track of whether a prime was detected earlier is placed in the stream of incoming lightweight spaceships. Thus, if it’s possible for two pairs to overlap, we will get lightweight spaceships colliding with the block, causing a mess.

To get around this problem, we use a device (known as a fanout, in green below) that duplicates the stream of lightweight spaceships. We then check for certain pairs on one stream, and the rest of the pairs on the other stream (these devices are outlined in blue below). Once we’re done, we merge the resulting streams of lightweight spaceships back together (using the devices in purple below).

To make this process a bit more explicit, I present a gun that computes prime pairs of the form (p,p+8). In particular, a lightweight spaceship will make it past the left edge of this pattern at about generation 1620+120N if and only if both N and N+8 are prime.

(p, p+8) prime calculator

• Java link: here
• RLE file: here

We now have all of the tools needed to build any pattern that computes prime pairs of the form (p, p+2k) as long as k = 1 or 2 (mod 3), though we may need to use the fanout device multiple times if it’s possible for more than one pair to overlap. If k = 0 (mod 3), however, it’s much more difficult to construct the desired pattern, because not only can you have overlapping prime pairs like (5, 11) and (7, 13), but you can have prime pairs in sequence such as (5, 11) and (11, 17). This problem can be remedied using the same tools as used in the (p,p+8) prime calculator, though you may need to use a lot of fanout devices to make things work. For example, computing the sexy primes using these tools would require at least four fanouts, and some clever elimination logic on each of the resulting five lightweight spaceship streams. I don’t feel up to that task myself, but it’s nice to know that we have a method for constructing a sexy prime calculator.