FRACTRAN

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, ... OEIS|id=A007542

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 OEIS|id=A034785

which are the prime powers of 2.

Explanation of FRACTRAN

A FRACTRAN program uses a potentially unlimited number of variables, each of which can store an arbitrarily large positive integer (FRACTRAN has no direct representation of negative integers, floating point numbers or text strings, although conventions could be adopted to represent these data types indirectly). [Proposed extensions to FRACTRAN include [http://www.esolangs.org/wiki/Fractran_plus_plus FRACTRAN++] and [http://home.nvg.org/~oerjan/esoteric/bag/ Bag] .] The state of a FRACTRAN program is represented by a single positive integer; the value of each variable is encoded as the exponent of a prime number in the prime factorization of that integer. For example, the number

:$$60=2^2 imes3^1 imes5^1, ,

represents a state in which one variable (which we will call V_2) holds the value 2 and two other variables (V_3 and V_5) hold the value 1. All other variables hold the value 0.

A FRACTRAN program is an ordered list of positive fractions. Each fraction in a FRACTRAN program represents an instruction that tests one or more variables, represented by the prime factors of its denominator. If the values of these variables are greater than 0, then they are decremented and the values of the variables represented by the prime factors of the numerator are incremented. For example:

:$$frac{10}{3}, ,

tests V_3; if V_3 is greater than 0 it subtracts 1 from V_3 and adds 1 to V_2 and V_5.

These test-decrement-increment instructions are the only instructions in a FRACTRAN program. This means that a FRACTRAN program has certain key features:

:*Each time a variable is tested, it is also decremented.:*The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.:*It is not possible for a FRACTRAN instruction to directly test if a variable is 0. However, an indirect test can be implemented by creating a default instruction that is placed after other instructions that test a particular variable.

The simplest FRACTRAN program is a single instruction such as

:$$frac{3}{2}, .

This program can be represented as a (very simple) finite state machine as follows:

:

When we write out the FRACTRAN instructions, we must put the state A instructions last, because state A has no state control flags. So as a FRACTRAN program, the multiplier becomes:

:$$frac{13}{21}, frac{385}{13}, frac{1}{7}, frac{3}{11}, frac{7}{2}, frac{1}{3}, ,

and input 2^"a" 3^"b" produces output 5^"ab". [This multiplier algorithm is described at the [http://www.esolangs.org/wiki/Fractran Esolang FRACTRAN page] .]

In a similar way, we can create a FRACTRAN "subtracter", and repeated subtractions allow us to create a "quotient and remainder" algorithm as follows:

:

Writing out the FRACTRAN program, we have:

:$$frac{91}{66}, frac{11}{13}, frac{1}{33}, frac{17}{11}, frac{95}{17}, frac{69}{133}, frac{19}{23}, frac{11}{19}, frac{1}{3}, ,

and input 2^"n" 3^"d" 11 produces output 5^"q" 7^"r" where "n" = "qd" + "r" and 0 &le; "r" < "d".

Conway's prime generating algorithm above is essentially a quotient and remainder algorithm within two loops. Given input of the form 2^"n" 7^"m" where 0 &le; "m" < "n", the algorithm tries to divide "n"+1 by each number from "n" down to 1, until it finds the largest number "k" that is a divisor of "n"+1. It then returns 2^"n"+1 7^"k"-1 and repeats. The only times that the sequence of state numbers generated by the algorithm produces a power of 2 is when "k" is 1 (so that the exponent of 7 is 0), which only occurs if the exponent of 2 is a prime. A step-by-step explanation of Conway's algorithm can be found in Havil(2007).

ee also

*Unlambda

References

*cite book
last = Conway
first = John H.
coauthors = Guy, Richard K.
title = The Book of Numbers
publisher = Springer-Verlag New York, Inc.
date = 1996
isbn = 038797993X
*cite book
last = Havil
first = Julian
title = Nonplussed!
publisher = Princeton University Press
date = 2007
isbn = 0691120560

External links

* [http://scienceblogs.com/goodmath/2006/10/prime_number_pathology_fractra.php "Prime Number Pathology: Fractran"]
*
* [http://brainwagon.org/?p=2207 "Prime Number Pathology"]
* [http://www.esolangs.org/wiki/Fractran FRACTRAN] -(Esolang wiki)