FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:
gives the following FRACTRAN program, called PRIMEGAME, which finds successive prime numbers:
Starting with n=2, this FRACTRAN program generates the following sequence of integers:
After 2, this sequence contains the following powers of 2:
The exponent part of these powers of two are primes, 2, 3, 5, etc.
A FRACTRAN program can be seen as a type of register machine where the registers are stored in prime exponents in the argument .
Using Gödel numbering, a positive integer can encode an arbitrary number of arbitrarily large positive integer variables. The value of each variable is encoded as the exponent of a prime number in the prime factorization of the integer. For example, the integer
represents a register state in which one variable (which we will call ) holds the value 2 and two other variables ( and ) hold the value 1. All other variables hold the value 0.
A FRACTRAN program is an ordered list of positive fractions. Each fraction represents an instruction that tests one or more variables, represented by the prime factors of its denominator. For example:
tests and . If and , then it subtracts 2 from and 1 from and adds 1 to and 1 to . For example:
Since the FRACTRAN program is just a list of fractions, these test-decrement-increment instructions are the only allowed instructions in the FRACTRAN language. In addition the following restrictions apply:
The simplest FRACTRAN program is a single instruction such as
This program can be represented as a (very simple) algorithm as follows:
Given an initial input of the form , this program will compute the sequence , , etc., until eventually, after steps, no factors of 2 remain and the product with no longer yields an integer; the program then stops with a final output of . It therefore adds two integers together.
We can create a "multiplier" by "looping" through the "adder". In order to do this we need to introduce states into our algorithm. This algorithm will take a number and produce :
State B is a loop that adds to and also moves to , and state A is an outer control loop that repeats the loop in state B times. State A also restores the value of from after the loop in state B has completed.
We can implement states using new variables as state indicators. The state indicators for state B will be and . Note that we require two state control indicators for one loop; a primary flag () and a secondary flag (). Because each indicator is consumed whenever it is tested, we need a secondary indicator to say "continue in the current state"; this secondary indicator is swapped back to the primary indicator in the next instruction, and the loop continues.
Adding FRACTRAN state indicators and instructions to the multiplication algorithm table, we have:
When we write out the FRACTRAN instructions, we must put the state A instructions last, because state A has no state indicators - it is the default state if no state indicators are set. So as a FRACTRAN program, the multiplier becomes:
With input 2<sup>a</sup>3<sup>b</sup> this program produces output 5<sup>ab</sup>.
In a similar way, we can create a FRACTRAN "subtractor", and repeated subtractions allow us to create a "quotient and remainder" algorithm as follows:
Writing out the FRACTRAN program, we have:
and input 2<sup>n</sup>3<sup>d</sup>11 produces output 5<sup>q</sup>7<sup>r</sup> where n = qd + r and 0 ⤠r < d.
Conway's prime generating algorithm above is essentially a quotient and remainder algorithm within two loops. Given input of the form where 0 ⤠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<sup>n+1</sup> 7<sup>k-1</sup> 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).
For this program, reaching the prime number 2, 3, 5, 7... requires respectively 19, 69, 281, 710,... steps .
A variant of Conway's program also exists, which differs from the above version by two fractions:
This variant is a little faster: reaching 2, 3, 5, 7... takes it 19, 69, 280, 707... steps . A single iteration of this program, checking a particular number N for primeness, takes the following number of steps:
where is the largest integer divisor of N and is the floor function.
In 1999, Devin Kilminster demonstrated a shorter, ten-instruction program:
For the initial input n = 10 successive primes are generated by subsequent powers of 10.
The following FRACTRAN program:
calculates the Hamming weight H(a) of the binary expansion of a i.e. the number of 1s in the binary expansion of a. Given input 2<sup>a</sup>, its output is 13<sup>H(a)</sup>. The program can be analysed as follows: