Fractran

From Esolang
(Redirected from FRACTRAN)
Jump to navigation Jump to search

See also wikipedia:FRACTRAN.

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