FRACTRAN
# FRACTRAN

FRACTRAN ist eine Turing-vollständige esoterische Programmiersprache des englischen Mathematikers John H. Conway. Ein FRACTRAN-Programm besteht aus einer endlichen Folge positiver Brüche $f_{1},f_{2},\dotsc ,f_{k}.$ Der Name FRACTRAN ist ein Wortspiel und bezieht sich auf die Programmiersprache FORTRAN (FORmula TRANslation = Formelübersetzung) und das englische Wort für Bruch (fraction). FRACTRAN heißt also so viel wie FRACtion TRANslation = Bruchübersetzung.

## FRACTRAN ausführen

FRACTRAN, von Conway auch als fraction game bezeichnet, wird folgendermaßen „gespielt“:

* Eine positive ganze Zahl $N$ als Startzahl wird nacheinander mit den Brüchen $f$ multipliziert, solange bis das Produkt $Nf$ wiederum eine ganze Zahl ist. In diesem Fall wird $N$ durch $Nf$ ersetzt und man beginnt mit der neuen Zahl wieder von vorne.
* Wenn keiner der Brüche eine ganze Zahl erzeugt, endet das Programm bzw. Spiel.

FRACTRAN lässt sich auch formaler beschreiben, wobei $P$ das FRACTRAN-Programm, $\{N_{n}\}$ die erzeugte Folge und $A_{n}$ die Menge aller Indizes ist, für die das Produkt $N_{n}f_{i}$ zu einer ganzen Zahl wird:

    $P=f_{1},f_{2},f_{3},\dotsc ,f_{k}\qquad (f_{i}\in \mathbb {Q} ^{+})$
    $\{N_{n}\}=N_{0},N_{1},N_{2},N_{3},\dotsc$
    $A_{n}=\{i\ |\ 1\leq i\leq k,\ N_{n}f_{i}\in \mathbb {N} \}$
    $N_{0}=N\qquad (N\in \mathbb {N} )$
    $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 erzeugt eine endliche oder auch unendliche Folge von natürlichen Zahlen. Wenn der letzte Bruch im FRACTRAN-Programm als Nenner eine 1 hat, ist die Folge der natürlichen Zahlen auf jeden Fall unendlich. Wenn ein früherer Bruch im FRACTRAN-Programm als Nenner eine 1 hat, werden die nachfolgenden Brüche beim Multiplizieren nie erreicht und sind somit unnötig für das Programm. Allerdings können auch FRACTRAN-Programme, in denen keiner der Nenner eine 1 ist, bei bestimmten Eingaben eventuell endlos laufen.

## Ein erstes Beispiel

Das kurze Programm

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

erzeugt mit der Startzahl $N=72$ die Folge $72,120,200,80,32.$ Aber was hat das mit einem Programm zu tun, warum ist die Startzahl 72 und warum endet das Programm?

### Das erste Beispiel genauer betrachtet

Um ein FRACTRAN-Programm besser zu verstehen, ist es sinnvoll, die Zahlen der erzeugten Folge in Primfaktoren zu zerlegen:

$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}.$ Wir betrachten jetzt in erster Linie die Exponenten der Startzahl $N=72=2^{a}\cdot 3^{b}$ als Eingaben in das Programm, also $a=3,b=2.$ Wenn wir uns nun die Exponenten der erzeugten Folge anschauen, dann sehen wir, dass zunächst durch zweimalige Multiplikation mit dem ersten Bruch der Exponent von 3 jeweils um 1 verringert und der Exponent von 5, der ursprünglich 0 war, um 1 vergrößert wird, bis der Exponent von 3 den Wert 0 erreicht hat. Da die nächsten beiden Zahlen der Folgen, nämlich 200 und 80, nicht durch 3, aber durch 5 geteilt werden können, kommt nun der zweite Bruch zweimal zum Tragen: der Exponent von 2 wird jeweils um 1 vergrößert und der Exponent von 5 um 1 verringert, bis auch er den Wert 0 erreicht hat. Da nun die Exponenten von 3 und 5 beide den Wert 0 haben, führt keiner der beiden Brüche bei der Multiplikation zu einer ganzen Zahl, das Programm endet und der Exponent von 2 ist die Summe der ursprünglichen Exponenten von 2 und 3.

Allgemein wird durch das obige FRACTRAN-Programm die Startzahl $N=2^{a}\cdot 3^{b}$ in die Zahl $N_{2b}=2^{a+b}$ überführt. Es handelte sich also um ein Additionsprogramm. Das hätte man mit dem FRACTRAN-Programm ${\frac {2}{3}}$ allerdings auch kürzer haben können, zumal es auch nur halb so viele Schritte bis zur Lösung benötigt.

## Weitere Beispiele

### Das (a - b) - Programm

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

Die Startzahl ist wiederum $N=2^{a}\cdot 3^{b},$ wobei a größer oder gleich b sein sollte. Die erzeugte Folge endet mit $N_{b}=2^{a-b}\cdot 3^{0}.$

### Das 2a - Programm

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

Die Startzahl ist $N=2^{a}.$ Die erzeugte Folge endet mit $N_{a}=2^{0}\cdot 3^{2a}.$

### Das max (a, b) - Programm

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

Die Startzahl ist $N=2^{a}\cdot 3^{b}.$ Nach max (a, b) Schritten endet die erzeugte Folge mit $N_{max(a,b)}=2^{0}\cdot 3^{0}\cdot 5^{max(a,b)}.$ Das Programm arbeitet folgendermaßen: Zunächst werden durch Multiplikation mit dem ersten Bruch ${\frac {5}{2\cdot 3}}$ die Werte von a und b gleichzeitig jeweils um 1 verringert, während c, das am Anfang 0 war, um 1 vergrößert wird, bis a oder b gleich 0 ist. Mit den beiden Brüchen ${\frac {5}{2}},{\frac {5}{3}}$ wird nun auch der Wert von a oder b, der noch nicht 0 war, schrittweise auf 0 gebracht, während c weiterhin um 1 vergrößert wird.

Das max (a, b) - Programm lässt sich sehr einfach zu einem min (a, b) - Programm umschreiben, indem die beiden letzten Zähler von 5 auf 1 geändert werden.

### Das Fibonacci - Programm

Das folgende FRACTRAN-Programm berechnet die n-te Fibonacci-Zahl $f_{n}$:

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

Die Startzahl ist $N=2^{f_{1}}\cdot 3^{f_{0}}\cdot 5^{n-1}.$ Die erzeugte Folge endet mit der Zahl $2^{f_{n}}$. So führt z. B. die Startzahl $31250=2^{1}\cdot 3^{0}\cdot 5^{6}$ zum Ergebnis $8192=2^{13}$, wobei 13 die 7. Fibonaccizahl ist.

### Conways PRIMEGAME

Das sicherlich bekannteste FRACTRAN-Programm ist Conways PRIMEGAME:

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

Mit der Startzahl $N=2$ wird eine Folge erzeugt, die in der richtigen Reihenfolge genau die Zweierpotenzen enthält, deren Exponent eine Primzahl ist. Mit anderen Worten, PRIMEGAME generiert alle Primzahlen, allerdings sehr langsam: $N_{19}=2^{2},N_{69}=2^{3},N_{281}=2^{5},N_{710}=2^{7},N_{2375}=2^{11}.$

## Ein Java-Programm

Das folgende Java-Programm multipliziert 5 mit 2: $N=288=2^{5}\cdot 3^{2},N_{42}=9765625=5^{10}.$

Da N im Verlauf des Programms sehr groß werden kann, ist es sinnvoll, das obige Programm so zu erweitern, dass nicht mehr die Zahl N, sondern nur noch die Exponenten von N verarbeitet werden.

