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 2x 3y, the following list gives output 5xy, 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 f0,…,fn 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 gi is given by
- g0 = q/p
- g1 = q/r
- gi+2 = a(fi)
- 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 qk, where k is the maximal number of q factors in the gi.
All fractions gi 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 qk 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