List of FRACTRAN programs to compute core sequences

This article is under construction.            

Please do not rely on any information it contains.            

Theoretically, FRACTRAN can compute any arithmetically defined sequence of integers. We will now attempt to give at least one FRACTRAN program for each core sequence in the OEIS.

On this page, the sequences of numerators and denominators are given without commas so as to facilitate input into an online FRACTRAN interpreter.

Prime numbers

The most famous FRACTRAN program is Conway's PRIMEGAME, which computes the prime numbers as exponents of powers of 2. The recommended initial value is 1. Some other values may still produce results, but some values may cause an infinite loop (see A272260).

Numerators	17 78 19 23 29 77 95 77 1 11 13 15 1 55	A202138
Denominators	91 85 51 38 33 29 23 19 17 13 11 2 7 1	A203363

Compared to the sieve of Eratosthenes, Conway's PRIMEGAME is a Rube Goldberg machine.

PLACEHOLDER FOR OTHER PRIME NUMBER PROGRAMS

Natural numbers, even and odd

By contrast, the program to compute the natural numbers (including 0) is exceedingly simple. The list of fractions consists entirely of the integer 2 (be sure to enter the implied numerator 1 in FRACTRAN implementations that require it). Start with 1 and get A001477, or start with 2 to get A000027.

The even numbers and the odd numbers are also easily obtained. Change the list of fractions to consist entirely of the integer 4. Start with 1 to get A005843, start with 2 to get A005408.

Just a tiny bit more involved than that is the program to compute the natural numbers repeated (A004526). Start with an initial value of 1, the sequence is given in the exponents of 2 (with an implied exponent 0 for 1 and 3).

Numerators	2 3
Denominators	3 1

If instead you use 3 as your initial value, the exponents of 2 instead give you A008619 (but that's not a core sequence).

Fibonacci numbers

John H. Conway also came up with a FRACTRAN program for the Fibonacci numbers, which he called FIBONACCIGAME. There are some important differences from PRIMEGAME. First, notice there are no integers in the list of rational numbers, which means that the process always comes to a halt, sooner or later, depending on the initial value.

Numerators	17 133 17 23 2233 23 31 74 31 41 129 41 13 1 1	A275483
Denominators	65 34 19 17 69 29 23 341 37 31 287 43 41 13 3	A275484

In order to obtain $F_{n}$, start with $78\times 5^{n-1}$ to obtain $2^{F_{n}}$ (see A000045 and A000301) when the process stops.

Others have come up with FRACTRAN programs that keep going, delivering $2^{F_{n+1}}$, $2^{F_{n+2}}$ and so on and so forth. PLACEHOLDER FOR SUCH PROGRAMS

Lucas numbers

PLACEHOLDER

References

• Julian Havil, Nonplussed! Mathematical Proof of Implausible Ideas. Princeton: Princeton University Press (2007): 174.