Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« Update: new territory for Online Soup Search | Main | The Continuing Search for a Microreflector »

2010 February 04

Engineered Objects
Prime numbers

The 'Primer' is a well-known Life pattern used to calculate prime numbers. The pattern expands in two directions, resembles a breeder, and emits a stream of spaceships representing prime numbers. The presence or absence of a spaceship at a particular generation indicates whether the number is prime or composite. It works by testing whether each integer is divisible by any smaller integer, apart from itself and 1. This is similar in principle to the Sieve of Eratosthenes.

Firstly, we present a new Primer by Jason Summers, which uses continual streams of spaceships to reflect the internal glider streams. Previous designs used static reflectors of periods 15 or 30. Jason's new Primer is substantially smaller than the previous prime number generators.

Jason Summers' new Prime number generator

In 2010, Jason engineered a Fermat Prime Calculator based on this new Primer and a Caber tosser he discovered. It is rigged up to explode if any Fermat Primes above 65537 are discovered. In other words, this machine exhibits infinite growth if and only if no Fermat Primes exist above 65537. It has been proven that all Fermat Primes up to and including 2^2^33+1 are composite, so this pattern will grow for at least 10^10^9 generations before halting.

The Fermat Prime Calculator

Because this is linked to an unsolved problem in mathematics, it is unknown whether this is an infinite-growth pattern, or whether it has a bounded (but astronomically high) final population. This serves to demonstrate that Life patterns are capable of unpredictable behaviour.

Nathaniel Johnston has been experimenting with the original Primer. After seeing Jason Summers' twin prime generator, he went on to engineer a cousin prime generator, quad prime generator and Mersenne prime generator. The latter is intimately linked to Jason's Fermat Prime Calculator: Instead of testing every number of the form 2^n+1, like the Fermat Prime Calculator, it tests every number of the form 2^n-1. These can only be prime if n is prime (try visualising the number in binary for a simple proof), so the device does indeed find all Mersenne primes. You can find further information about Nathaniel's patterns on his weblog.

Nathaniel's Mersenne Prime Generator

Mersenne primes have gathered recent interest after the discovery of two 12-million-digit primes. The first of these claimed a $100 000 prize for being the first prime with 10-million or more digits. Similar prizes, of $150 000 and $200 000, have been offered for the first 100-million-digit and one-billion-digit primes, respectively.

Prime-period oscillators represent another connection between Life and prime numbers. The blinker, pulsar and fumarole are oscillators with periods equal to the first three prime numbers (2,3 and 5, respectively). But what about larger prime numbers? Gabriel Nivasch and Dave Greene have built 11-digit and 12-digit prime-period oscillators, each comprising a drive gun (Herschel loop) and a string of pulse dividers. When the glider passes through all of the pulse dividers, it alters the phase of the drive gun.

Adam P. Goucher has used a similar principle to create a 13395-digit prime-period oscillator. It consists of a densely populated area of period-doublers and period-quadruplers, attached to a large p8192 Herschel loop. Returning gliders advance the Herschel by one tick, giving the oscillator the all-important "-1" adjustment to form a Mersenne prime. In case you were wondering, the prime in question is 2^44497-1.