Wikipedia
FRACTRAN
FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:
- for the first fraction f in the list for which nf is an integer, replace n by nf
- repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
In The Book of Numbers, John Conway and Richard Guy gave a formula for primes in FRACTRAN:
$\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)$Starting with n=2, this FRACTRAN program generates the following sequence of integers:
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...After 2, this sequence contains the following powers of 2:
2 = 4, 2 = 8, 2 = 32, 2 = 128, 2 = 2048, 2 = 8192, 2 = 131072, 2 = 524288, …
which are the prime powers of 2.