FRACTRAN
Turing-complete esoteric programming language invented by John Conway
title: "FRACTRAN" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["models-of-computation", "esoteric-programming-languages", "recreational-mathematics"] description: "Turing-complete esoteric programming language invented by John Conway" topic_path: "technology/programming-languages" source: "https://en.wikipedia.org/wiki/FRACTRAN" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Turing-complete esoteric programming language invented by John Conway ::
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:
- for the first fraction f in the list for which nf is an integer, replace n by nf
- repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
gives the following FRACTRAN program, called PRIMEGAME, which finds successive prime numbers:
\left( \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}{2}, \frac{1}{7}, \frac{55}{1} \right)
Starting with n=2, this FRACTRAN program generates the following sequence of integers:
- 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... , i.e. the sequence of PRIMEGAME numbers
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
The exponent part of these powers of two are primes, 2, 3, 5, etc.
Understanding a FRACTRAN program
A FRACTRAN program can be seen as a type of register machine where the registers are stored in prime exponents in the argument n.
Using Gödel numbering, a positive integer n can encode an arbitrary number of arbitrarily large positive integer variables.Gödel numbering cannot be directly used for negative integers, floating point numbers or text strings, although conventions could be adopted to represent these data types indirectly. Proposed extensions to FRACTRAN include FRACTRAN++ and Bag. 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
60 = 2^2 \times 3^1 \times 5^1
represents a register 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 represents an instruction that tests one or more variables, represented by the prime factors of its denominator. For example:
f_1 = \frac{21}{20} = \frac{3 \times 7}{2^2 \times 5^1}
tests v_2 and v_5. If v_2 \ge 2 and v_5 \ge 1, then it subtracts 2 from v_2 and 1 from v_5 and adds 1 to v_3 and 1 to v_7. For example:
60 \cdot f_1 = 2^2 \times 3^1 \times 5^1 \cdot \frac{3 \times 7}{2^2 \times 5^1} = 3^2 \times 7^1
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:
- Each time an instruction is executed, the variables that are tested are 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.).
Creating simple programs
Addition
The simplest FRACTRAN program is a single instruction such as
\left( \frac{3}{2} \right)
This program can be represented as a (very simple) algorithm as follows:
::data[format=table] | FRACTRAN instruction | Condition | Action | |---|---|---| | \frac{3}{2} | v_2 0 | Subtract 1 from v_2 Add 1 to v_3 | | | v_2 = 0 | Stop | ::
Given an initial input of the form 2^a 3^b, this program will compute the sequence 2^{a-1} 3^{b+1}, 2^{a-2} 3^{b+2}, etc., until eventually, after a steps, no factors of 2 remain and the product with \frac{3}{2} no longer yields an integer; the program then stops with a final output of 3^{a + b}. It therefore adds two integers together.
Multiplication
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 2^a 3^b and produce 5^{ab}:
::data[format=table]
| Current state | Condition | Action | Next state |
|---|---|---|---|
| A | v_7 0 | Subtract 1 from v_7 | |
| Add 1 to v_3 | A | ||
| v_7 = 0 and | |||
| v_2 0 | Subtract 1 from v_2 | B | |
| v_7 = 0 and | |||
| v_2 = 0 and | |||
| v_3 0 | Subtract 1 from v_3 | A | |
| v_7 = 0 and | |||
| v_2 = 0 and | |||
| v_3 = 0 | Stop | ||
| B | v_3 0 | Subtract 1 from v_3 | |
| Add 1 to v_5 | |||
| Add 1 to v_7 | B | ||
| v_3 = 0 | None | A | |
| :: |
State B is a loop that adds v_3 to v_5 and also moves v_3 to v_7, and state A is an outer control loop that repeats the loop in state B v_2 times. State A also restores the value of v_3 from v_7 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 v_{11} and v_{13}. Note that we require two state control indicators for one loop; a primary flag (v_{11}) and a secondary flag (v_{13}). 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:
::data[format=table] | FRACTRAN instruction | Current state | State indicators | Condition | Action | Next state | |---|---|---|---|---|---| | \frac{3}{7} | A | None | v_7 0 | Subtract 1 from v_7 Add 1 to v_3 | A | | \frac{11}{2} | v_7 = 0 and v_2 0 | Subtract 1 from v_2 | B | | | | \frac{1}{3} | v_7 = 0 and v_2 = 0 and v_3 0 | Subtract 1 from v_3 | A | | | | | v_7 = 0 and v_2 = 0 and v_3 = 0 | Stop | | | | | \frac{5 \cdot 7 \cdot 13}{3 \cdot 11}, \frac{11}{13} | B | v_{11}, v_{13} | v_3 0 | Subtract 1 from v_3 Add 1 to v_5 Add 1 to v_7 | B | | \frac{1}{11} | v_3 = 0 | None | A | | | ::
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:
\left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{3} \right)
With input 2a3b this program produces output 5ab. A similar multiplier algorithm is described at the Esolang FRACTRAN page.
::figure[src="https://upload.wikimedia.org/wikipedia/commons/6/61/FRACTRANmult0.gif" caption="The above FRACTRAN program, computing 3 times 2 (so that its input is 2^3\times 3^2=72 and its output should be 5^6 because 3 times 2 equals 6."] ::
Subtraction and division
In a similar way, we can create a FRACTRAN "subtractor", and repeated subtractions allow us to create a "quotient and remainder" algorithm as follows:
::data[format=table] | FRACTRAN instruction | Current state | State indicators | Condition | Action | Next state | |---|---|---|---|---|---| | \frac{7 \cdot 13}{2 \cdot 3 \cdot 11}, \frac{11}{13} | A | v_{11}, v_{13} | v_2 0 and v_3 0 | Subtract 1 from v_2 Subtract 1 from v_3 Add 1 to v_7 | A | | \frac{1}{3 \cdot 11} | v_2 = 0 and v_3 0 | Subtract 1 from v_3 | X | | | | \frac{5 \cdot 17}{11} | v_3 = 0 | Add 1 to v_5 | B | | | | \frac{3 \cdot 19}{7 \cdot 17}, \frac{17}{19} | B | v_{17}, v_{19} | v_7 0 | Subtract 1 from v_7 Add 1 to v_3 | B | | \frac{11}{17} | v_7 = 0 | None | A | | | | \frac{1}{3} | X | | v_3 0 | Subtract 1 from v_3 | X | | | v_3 = 0 | Stop | | | | ::
Writing out the FRACTRAN program, we have:
\left( \frac{91}{66}, \frac{11}{13}, \frac{1}{33}, \frac{85}{11}, \frac{57}{119}, \frac{17}{19}, \frac{11}{17}, \frac{1}{3} \right)
and input 2n3d11 produces output 5q7r where n = qd + r and 0 ≤ r
Conway's prime algorithm
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 ≤ m n+1 7k-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).
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: \left( \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} \right)
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: N - 1 + (6N+2)(N-b) + 2 \sum\limits^{N-1}_{d=b} \left\lfloor \frac{N}{d} \right\rfloor, where b is the largest integer divisor of N and \lfloor x \rfloor is the floor function.
In 1999, Devin Kilminster demonstrated a shorter, ten-instruction program: \left( \frac{7}{3}, \frac{99}{98}, \frac{13}{49}, \frac{39}{35}, \frac{36}{91}, \frac{10}{143}, \frac{49}{13}, \frac{7}{11}, \frac{1}{2}, \frac{91}{1} \right). For the initial input n = 10 successive primes are generated by subsequent powers of 10.
Other examples
The following FRACTRAN program:
\left( \frac{3 \cdot 11}{2^2 \cdot 5} , \frac{5}{11}, \frac{13}{2 \cdot 5}, \frac{1}{5}, \frac{2}{3}, \frac{2 \cdot 5}{7}, \frac{7}{2} \right)
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 2a, its output is 13H(a). The program can be analysed as follows:
::data[format=table] | FRACTRAN instruction | Current state | State indicators | Condition | Action | Next state | |---|---|---|---|---|---| | \frac{3 \cdot 11}{2^2 \cdot 5}, \frac{5}{11} | A | v_5, v_{11} | v_2 1 | Subtract 2 from v_2 Add 1 to v_3 | A | | \frac{13}{2 \cdot 5} | v_2 = 1 | Subtract 1 from v_2 Add 1 to v_{13} | B | | | | \frac{1}{5} | v_2 = 0 | None | B | | | | \frac{2}{3} | B | None | v_3 0 | Subtract 1 from v_3 Add 1 to v_2 | B | | \frac{2 \cdot 5}{7} | v_3 = 0 and v_7 0 | Subtract 1 from v_7 Add 1 to v_2 | A | | | | \frac{7}{2} | v_3 = 0 and v_7 = 0 and v_2 0 | Subtract 1 from v_2 add 1 to v_7 | B | | | | | v_2 = 0 and v_3 = 0 and v_7 = 0 | Stop | | | | ::
Notes
References
- {{cite journal | last = Guy | first = Richard K. | author-link = Richard Kenneth Guy | title = Conway's Prime Producing Machine | url = https://www.tandfonline.com/doi/abs/10.1080/0025570X.1983.11977011 | journal = Mathematics Magazine | volume = 56 | issue = 1 | pages = 26–33 | year = 1983 | publisher = Taylor & Francis | doi = 10.1080/0025570X.1983.11977011| url-access = subscription}}
- {{cite book | last = Conway | first = John H. | title = Open Problems in Communication and Computation | chapter = FRACTRAN: A Simple Universal Programming Language for Arithmetic | pages = 4–26 | doi = 10.1007/978-1-4612-4808-8_2 | publisher = Springer-Verlag New York, Inc. | year = 1987 | isbn = 978-1-4612-9162-6
- {{cite book | last1 = Conway | first1 = John H. | last2 = Guy |first2=Richard K. | title = The Book of Numbers | publisher = Springer-Verlag New York, Inc. | year = 1996 | isbn = 0-387-97993-X | url-access = registration | url = https://archive.org/details/bookofnumbers0000conw
- {{cite book | last = Havil | first = Julian | title = Nonplussed! | publisher = Princeton University Press | year = 2007 | isbn = 978-0-691-12056-0 | url-access = registration | url = https://archive.org/details/nonplussedmathem00havi
References
- {{harvnb. Guy. 1983. Conway. Guy. 1996
- {{harvnb. Guy. 1983
- {{harvnb. Havil. 2007
- John Baez, [http://golem.ph.utexas.edu/category/2006/10/puzzle_4.html Puzzle #4], The ''n''-Category Café
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::