July 6, 2012
The British mathematician John Horton Conway, famous for inventing the cellular automata Game of Life, also invented an esoteric programming language called fractran in which commands are represented as fractions; for instance, the primegame program generates prime numbers:
17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1
Fractran has two rules:
1. Find the first fraction f in the list for which nf is an integer, output nf, and set n ← nf.
2. Repeat the first rule, but halt if no product nf is integral.
For example, given an initial 2, the sequence of values produced by the above program begins 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, …. (A007542).
The program is called primegame because the exponents of each number in the sequence that is a power of 2 form the list of prime numbers. For instance, the number 4 in the sequence is 22, for which the exponent 2 is the first prime. Fifty steps later the sequence takes the value 8 = 23. After another 211 steps the sequence takes the value 32 = 25. And so on, generating all of the prime numbers in sequence.
Your task is to write a fractran interpreter and use it to generate prime numbers using primegame. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.