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 fin 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 formula for primes in FRACTRAN:[note 1]
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)
After 2, this sequence contains the following powers of 2:
(sequence A034785 in the OEIS)
which are the prime powers of 2.
References
- ^John Baez, Puzzle #4, The n-Category Café
- Conway, John H. (1987). “FRACTRAN: A simple universal programming language for arithmetic”. Open Problems in Communication and Computation. Springer-Verlag New York, Inc.: 4–26. doi:10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6.
- Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc. ISBN 0-387-97993-X.
- Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 0-691-12056-0.
- Roberts, Siobhan (2015). “Criteria of virtue”. Genius At Play – The Curious Mind of John Horton Conway. Bloomsbury. pp. 115–119. ISBN 978-1-62040-593-2.