Fractran

FRACTRAN

Designed by	John Conway
Appeared in	1986
Computational class	Turing-complete
Reference implementation	Unimplemented

See also wikipedia:FRACTRAN.

Fractran is a language and associated computational model introduced by John Conway in their 1986 article, "FRACTRAN: A Simple Universal Programming Language for Arithmetic."

In Fractran, a program consists of a finite list of positive, rational numbers. The input to a program is a positive integer n. The list is then searched in order, for a rational number p/q such that np/q is an integer. Then n is replaced by np/q and the search is restarted from the beginning of the list. The program halts when no such number p/q can be found, and the final n becomes the output from the program.

The power of this formalism comes from viewing numbers as products of prime powers, a form of mAME. For example, if the input is 2^x 3^y, the following list gives output 5^xy, essentially multiplying x by y:

13/21, 385/13, 1/7, 3/11, 7/2, 1/3
  or, after prime factorization,
13/(3*7), (5*7*11)/13, 1/7, 3/11, 7/2, 1/3

John Conway made the following program for producing 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/14, 15/2, 55/1

If you start with n=2, it will go through exactly those powers of 2 whose exponents are prime numbers.

In 1999, this was shortened by Devin Kilminster (then a Ph.D student at the University of Western Australia, now a scientist at the Meteorological Service of New Zealand) to the following:

7/3 99/98 13/49 39/35 36/91 10/143 49/13 7/11 1/2 91/1

When started with n=10, this produces a sequence of powers of 10 whose exponents are successive primes.

Kilminster has since shortened the above program to produce a prime program using only nine fractions:

3/11 847/45 143/6 7/3 10/91 3/7 36/325 1/2 36/5

Squeezing fraction size

It is possible to modify any Fractran program so that its fractions are arbitrarily close to 1 in size but it can still perform the same computations.

Let f₀,…,f_n be the fractions of the program.

Given any ε>0, choose primes p,q,r; p<q<r<p(1+ε), that are not already factors in the program. (Possible by the Wikipedia:Prime number theorem.)

Then a new list of fractions g_i is given by

g₀ = q/p

g₁ = q/r

g_i+2 = a(f_i)

a(x) = x * (p/q)^{round(-log x/log(p/q))}, x≥1

a(x) = x * (r/q)^{round(-log x/log(r/q))}, x≤1

All the new fractions so defined are within the range (1/(1+ε), 1+ε).

The input to the new program is the input to the old program multiplied by q^k, where k is the maximal number of q factors in the g_i.

All fractions g_i preserve the sum of the exponents of p, q and r, and the first two shuffle these back to q, to ensure that the number always contains q^k for the remaining fractions.

Interpreter

   frac=: ({~ 1 i.~(=<.))@:* NB. this is a small interpreter for fractran in J.
   cp  =: 17r91 78r85 19r51 23r38 29r33 77r29 95r23 77r19 1r17 11r13 13r11 15r14 15r2 55r1 NB. Conway Primer, example program.
   cp frac 2
15
   cp frac 15
825
   cp frac 825
725
   cp frac^:(i.10) 2                        NB. iterating.
2 15 825 725 1925 2275 425 390 330 290
   (#~ (=<.))@:(2&^.) cp frac^:(i.1e4) 2    NB. generating primes.
1 2 3 5 7 11 13 17
   genp=: 4 : '(#~ (=<.))@:(a&^.) x frac^:(i.b) a[#''a b''=.y' NB. genearlized.
   cp genp 2;1e4
1 2 3 5 7 11 13 17
   kilm=: 3r11 847r45 143r6 7r3 10r91 3r7 36r325 1r2 36r5 NB. Kilminster's program.
   kilm genp 10;1e4
1 2 3 5 7 11 13 17 19

See also

• mAME
• Bag
• Fractran++
• Collatz function
• Minsky machine
• Piece of cake
• ChooseNumber

External resources

• Conway 1987, a reprint of Conway's original article
• Fractran on Mathworld
• "Prime Number Pathology: Fractran" (Good Math, Bad Math blog, 2006-10-27)
• Fractran self-interpreter by Jesse Beder (from this Stack Overflow thread)
• Fast fractran interpreter by pimlu, source code for interpreter, article explaining background and how interpreter works
• An open source, compact and fast FRACTRAN interpreter written in the open source SNOBOL5 language.
• An in memoriam post shortly after John H. Conway's death mentioning that Conway ran a Fractran program that finds prime numbers
• Another programming language that compiles directly to FRACTRAN.