# Fractran

*See also wikipedia:FRACTRAN.*

Designed by | John Conway |
---|---|

Appeared in | 1986 |

Computational class | Turing-complete |

Reference implementation | Unimplemented |

File extension(s) | {{{files}}} |

**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. 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*_{0},…,*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*_{0}=*q*/*p**g*_{1}=*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

## 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