# Fractran

**Fractran** is a game/computational model/language by John Conway.

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

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