FRACTRAN

From Wikipedia, the free encyclopedia

FRACTRAN is a Turing-complete functional esoteric programming language invented by the mathematician John Conway. FRACTRAN programs are given as a list of fractions which are applied to a single argument p as follows:

multiply p by each fraction ƒ in the list in turn until pƒ is an integer; replace p by pƒ and repeat;
halt if no member of the list produces an integer when multiplied by p. This algorithm can be implemented very simply; for example, in J, a basic FRACTRAN interpretor might be (*{~1 i.~[@(=<.)@:*).

Conway gave an interesting formula for primes in FRACTRAN:

$\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1}.$

Starting with p=2, this FRACTRAN program generates the following sequence of integers:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (sequence A007542 in OEIS)

After 2, this sequence contains the following powers of 2:

$2^2=4,\, 2^3=8,\, 2^5=32,\, 2^7=128,\, 2^{11}=2048,\, 2^{13}=8192,\, 2^{17}=131072,\, 2^{19}=524288,\, \dots$ (sequence A034785 in OEIS)

which are the prime powers of 2.

[edit] See also

Unlambda

[edit] Further reading

Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc.. ISBN 038797993X.
Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 0691120560.