FRACTRAN

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: Conway 1987 gives the following FRACTRAN program, called PRIMEGAME, which finds successive prime numbers:

(sequence A034785 in the OEIS) 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.

[note 1] The value of each variable is encoded as the exponent of a prime number in the prime factorization of the integer.

represents a register state in which one variable (which we will call

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.

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

steps, no factors of 2 remain and the product with

no longer yields an integer; the machine then stops with a final output of

We can create a "multiplier" by "looping" through the "adder".

In order to do this we need to introduce states into our algorithm.

Note that we require two state control indicators for one loop; a primary flag (

With input 2a3b this program produces output 5ab.

[note 2] 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 2n3d11 produces output 5q7r where n = qd + r and 0 ≤ r < d. Conway's prime generating algorithm above is essentially a quotient and remainder algorithm within two loops.

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 (sequence A007547 in the OEIS).

A variant of Conway's program also exists,[1] 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 (sequence A007546 in the OEIS).

A single iteration of this program, checking a particular number N for primeness, takes the following number of steps:

[2] In 1999, Devin Kilminster demonstrated a shorter, ten-instruction program:[3]

For the initial input n = 10 successive primes are generated by subsequent powers of 10.

calculates the Hamming weight H(a) of the binary expansion of a i.e. the number of 1s in the binary expansion of a.