Last week we saw a few ways to (try to) generate prime numbers with simple formulas. I will now describe a much more puzzling (and recreational) method. The following numbers specify everything you need: $$\left(\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right).$$ To run this “game,” the rules are as follows: Start with value \(v = 2\). At each step, find the first fraction \(f\) in the list so that \(v \cdot f\) is an integer, and replace the value \(v\) by this integer. Repeat indefinitely (or until no such \(f\) can be found). The beginning of the computation looks like this:

1. Start with value \(v = 2\).
2. The first fraction \(f\) in the list such that \(2\cdot f\) is an integer is \(f=15/2\), so the new value \(v\) is \(2 \cdot 15/2 = 15\).
3. The first \(f\) in the list with \(15 \cdot f\) an integer is \(f=55/1\), so the new \(v\) is \(15 \cdot 55/1 = 825\).
4. The first \(f\) with \(825 \cdot f\) an integer is \(29/33\), so set \(v = 825 \cdot 29/33 = 725\).

And so on.

Continuing as above, the list of values looks like 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, … .

But what does this have to do with primes? The list of fractions was carefully constructed so that many powers of 2 will appear, in exactly the following order: $$2^1, 2^2, 2^3, 2^5, 2^7, 2^{11}, 2^{13}, 2^{17}, \ldots .$$ Indeed, except for \(2^1\) (the starting value), any power of two obtained by this process will have a prime exponent, and all primes will appear in this way (in order)! This is a very special property of the chosen list of fractions, and different lists give rise to vastly different output sequences.

In fact, you can think of this procedure as a programming language, where the list of fractions and the starting value constitute your “program.” This language is called FRACTRAN, and both the language and the above prime-enumerating program were designed by John Conway. What else is this language capable of computing? Lots! FRACTRAN can compute anything that modern computers could—but much less efficiently. (In Theoretical Computer Science terminology, FRACTRAN is turing complete.) See the Wikipedia page for more information, as well as an explanation of why the above program works.