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.
Ofer Abarbanel – Executive Profile
Ofer Abarbanel is a 25 year securities lending broker and expert who has advised many Israeli regulators, among them the Israel Tax Authority, with respect to stock loans, repurchase agreements and credit derivatives. Founder of TBIL.co STATX Fund.