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. Conway 1987 gives the following FRACTRAN program, called PRIMEGAME, which finds successive 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 2 , 1 7 , 55 1 ) {\displaystyle \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}{2}},{\frac {1}{7}},{\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, ... (sequence A007542 in the OEIS), i.e. the sequence of PRIMEGAME numbers After 2, this sequence contains the following powers of 2: 2 2 = 4 , 2 3 = 8 , 2 5 = 32 , 2 7 = 128 , 2 11 = 2048 , 2 13 = 8192 , 2 17 = 131072 , 2 19 = 524288 , … {\displaystyle 2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots } (sequence A034785 in the OEIS) The exponent part of these powers of two are primes, 2, 3, 5, etc.