FRACTRAN (Ofer Abarbanel online library)

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:

  1. for the first fraction fin the list for which nf is an integer, replace n by nf
  2. 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

  1. ^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 online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library