FRACTRAN

FRACTRAN is a Turing-complete esoteric programming language developed by the English mathematician John H. Conway . A FRACTRAN program consists of a finite sequence of positive fractions. The name FRACTRAN is a play on words and refers to the programming language FORTRAN (FORmula TRANslation = formula translation) and the English word for fraction . FRACTRAN means something like FRACtion TRANslation = fractional translation. ${\displaystyle f_{1},f_{2},\dotsc ,f_{k}.}$

Execute FRACTRAN

FRACTRAN, also called fraction game by Conway , is "played" as follows:

1. A positive whole number as a starting number is multiplied by the fractions one after the other until the product is again a whole number. In this case, is replaced by and you start over with the new number. ${\displaystyle N}$ ${\displaystyle f}$ ${\displaystyle Nf}$ ${\displaystyle N}$ ${\displaystyle Nf}$
2. If none of the fractions produce an integer, the program or game ends.

FRACTRAN can also be described more formally, where the FRACTRAN program is the sequence generated and the set of all indices for which the product becomes an integer: ${\displaystyle P}$ ${\displaystyle \{N_{n}\}}$ ${\displaystyle A_{n}}$ ${\displaystyle N_{n}f_{i}}$

${\displaystyle P=f_{1},f_{2},f_{3},\dotsc ,f_{k}\qquad (f_{i}\in \mathbb {Q} ^{+})}$

${\displaystyle \{N_{n}\}=N_{0},N_{1},N_{2},N_{3},\dotsc }$

${\displaystyle A_{n}=\{i\ |\ 1\leq i\leq k,\ N_{n}f_{i}\in \mathbb {N} \}}$

${\displaystyle N_{0}=N\qquad (N\in \mathbb {N} )}$

${\displaystyle N_{n+1}={\begin{cases}N_{n}f_{i},&{\text{wenn }}i=\min A_{n}\\{\text{undefiniert}},&{\text{wenn }}A_{n}=\emptyset \end{cases}}}$

FRACTRAN generates a finite or also an infinite sequence of natural numbers. If the last fraction in the FRACTRAN program has a 1 as a denominator, the sequence of natural numbers is definitely infinite. If an earlier fraction in the FRACTRAN program has a 1 as its denominator, the subsequent fractions are never reached during multiplication and are therefore unnecessary for the program. However, FRACTRAN programs in which none of the denominators is a 1 can possibly run endlessly with certain inputs.

A first example

The short program

${\displaystyle {\frac {5}{3}},{\frac {2}{5}}}$

generates the sequence with the start number But what does this have to do with a program, why is the start number 72 and why does the program end? ${\displaystyle N=72}$ ${\displaystyle 72,120,200,80,32.}$

A closer look at the first example

In order to better understand a FRACTRAN program, it makes sense to decompose the numbers of the generated sequence into prime factors:

${\displaystyle 2^{3}\cdot 3^{2},\ 2^{3}\cdot 3^{1}\cdot 5^{1},\ 2^{3}\cdot 3^{0}\cdot 5^{2},\ 2^{4}\cdot 3^{0}\cdot 5^{1},\ 2^{5}\cdot 3^{0}\cdot 5^{0}.}$We are now primarily looking at the exponents of the starting number as inputs into the program, so if we now look at the exponents of the generated sequence, we see that by multiplying twice with the first fraction, the exponent of 3 is reduced by 1 and the exponent of 5, which was originally 0, is increased by 1 until the exponent of 3 reaches the value 0. Since the next two numbers in the sequence, namely 200 and 80, cannot be divided by 3 but by 5, the second fraction now comes into play twice: the exponent of 2 is increased by 1 and the exponent of 5 is decreased by 1 until it too has reached the value 0. Since the exponents of 3 and 5 both have the value 0, neither of the two fractions leads to an integer during multiplication, the program ends and the exponent of 2 is the sum of the original exponents of 2 and 3. ${\displaystyle N=72=2^{a}\cdot 3^{b}}$ ${\displaystyle a=3,b=2.}$

In general, the above FRACTRAN program converts the starting number into the number . So it was an addition program. With the FRACTRAN program, however, this could have been shorter, especially since it only takes half as many steps to find a solution. ${\displaystyle N=2^{a}\cdot 3^{b}}$ ${\displaystyle N_{2b}=2^{a+b}}$ ${\displaystyle {\frac {2}{3}}}$

Further examples

The (a - b) program

${\displaystyle {\frac {1}{6}}}$

The starting number is again where a should be greater than or equal to b. The generated sequence ends with ${\displaystyle N=2^{a}\cdot 3^{b},}$ ${\displaystyle N_{b}=2^{a-b}\cdot 3^{0}.}$

The 2a program

${\displaystyle {\frac {9}{2}}}$

The starting number is The generated sequence ends with ${\displaystyle N=2^{a}.}$ ${\displaystyle N_{a}=2^{0}\cdot 3^{2a}.}$

The max (a, b) program

${\displaystyle {\frac {5}{6}},{\frac {5}{2}},{\frac {5}{3}}}$

The starting number is After max (a, b) steps the generated sequence ends with The program works as follows: First, by multiplying by the first fraction, the values ​​of a and b are simultaneously reduced by 1, while c, which was 0 at the beginning, is increased by 1 until a or b equals 0. With the two fractions , the value of a or b, which was not yet 0, is now gradually brought to 0, while c continues to be increased by 1. ${\displaystyle N=2^{a}\cdot 3^{b}.}$ ${\displaystyle N_{max(a,b)}=2^{0}\cdot 3^{0}\cdot 5^{max(a,b)}.}$ ${\displaystyle {\frac {5}{2\cdot 3}}}$ ${\displaystyle {\frac {5}{2}},{\frac {5}{3}}}$

The max (a, b) program can be very easily rewritten to a min (a, b) program by changing the last two counters from 5 to 1.

The Fibonacci Program

The following FRACTRAN program calculates the nth Fibonacci number : ${\displaystyle f_{n}}$

${\displaystyle {\frac {91}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {399}{34}},{\frac {17}{19}},{\frac {1}{17}},{\frac {2}{7}},{\frac {187}{5}},{\frac {1}{3}}}$

The starting number is The generated sequence ends with the number . So z. B. the starting number for the result , where 13 is the 7th Fibonacci number. ${\displaystyle N=2^{f_{1}}\cdot 3^{f_{0}}\cdot 5^{n-1}.}$ ${\displaystyle 2^{f_{n}}}$ ${\displaystyle 31250=2^{1}\cdot 3^{0}\cdot 5^{6}}$ ${\displaystyle 8192=2^{13}}$

Conway's PRIMEGAME

The most famous FRACTRAN program is Conway's PRIMEGAME:

${\displaystyle {\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}}}$

With the starting number , a sequence is generated that contains exactly the powers of two in the correct order, the exponent of which is a prime number . In other words, PRIMEGAME generates all prime numbers, but very slowly: ${\displaystyle N=2}$ ${\displaystyle N_{19}=2^{2},N_{69}=2^{3},N_{281}=2^{5},N_{710}=2^{7},N_{2375}=2^{11}.}$

A Java program

The following Java program multiplies 5 by 2: ${\displaystyle N=288=2^{5}\cdot 3^{2},N_{42}=9765625=5^{10}.}$

public class Fractran {
    public static void main(String[] args) {
        long N = 288;
        long[] zaehler = {455, 11, 1, 3, 11, 1};
        long[] nenner  = {33, 13, 11, 7, 2, 3};
        int i = 0, j;
        boolean halt = false;
        System.out.println(i + ": " + N);
        while (!halt) {
            j = 0;
            while (!halt && ((N*zaehler[j])%nenner[j] != 0)) {
                j++;
                if (j == zaehler.length) halt = true;
            }
            i++;
            if (!halt) {
                N = (N*zaehler[j])/nenner[j];
                System.out.println(i + ": " + N);
            }
        }
    }
}

Since N can become very large in the course of the program, it makes sense to expand the above program so that only the exponents of N are no longer processed, but only.

Individual evidence

1. ^ JH Conway: FRACTRAN: A Simple Universal Programming Language for Arithmetic. In: T. Jeffrey C. Lagarias (Ed.): The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Soc., 2010, ISBN 978-0-8218-4940-8 , pp. 249-264.
2. ↑ Dimitri Hendriks: FRACTRAN , 2011 (PDF; 256 kB)
3. ^ The On-Line Encyclopedia of Integer Sequences, episode A007542

literature

• John Horton Conway : FRACTRAN: A Simple Universal Programming Language for Arithmetic. In: Thomas M. Cover , B. Gopinath: Open Problems in Communication and Computation. Springer-Verlag, 1987, ISBN 0-387-96621-8 , pp. 4-26.
• Julian Havil: Amazed ?! : Mathematical proofs of incredible ideas. Springer-Verlag, Berlin / Heidelberg 2009, ISBN 978-3-642-32318-8 , pp. 155-170.
• Dominic Olivastro: The Chinese Triangle: The trickiest riddles from 10,000 years. Zweiausendeins, Frankfurt 2006, ISBN 3-86150-764-1 , pp. 30-38.

Web links

• Online calculator for FRACTRAN programs