Fractran ist eine Programmiersprache von John Horton Conway. Man definiert einen Startwert i und ein Programm, das aus einer Liste von Brüchen besteht. Das Programm läuft ab, indem nacheinander für alle Brüche getestet wird, ob das Produkt eines Bruchs und i eine natürliche Zahl ist. Wenn ja, dann ist dieses Produkt der neue Wert von i und der Test beginnt wieder mit dem ersten Bruch. Erfüllt kein Bruch die Bedingung, dann ist das Programm beendet.
Wird als Startwert 2 und als Programm 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1 verwendet, dann kann man alle Primzahlen ermitteln, indem man für jedes weitere berechnete i testet, ob es eine natürliche Zahl p mit der Bedingung 2^p=i gibt, wobei p dann die nächste Primzahl ist.
Es gibt auch Fractran-Programme, die die n.-Stelle von PI berechnen oder die Fibonacci-Folge. Unter http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/fractran gibt es eine Sammlung von eMails, in der auch Conway einen Beweis für das Primzahlenprogramm angibt. Daraus kann ableiten, daß der der Algorithmus wahrscheinlich nicht für große Primzahlen geeignet ist, da er für jede zu testende Primzahl n alle Zahlen von n-1 bis 1 durchgeht, um die Teilbarkeit zu prüfen. Interessanterweise sind in dem Programm unter http://mathworld.wolfram.com/Fractran.html zwei Brüche anders, es scheint aber damit zu laufen.
Eine C-Implementierung von mir (basierend auf einer Python-Implementierung) erzeugte für die ersten 100 Millionen Durchgänge in 415 Sekunden auf meinem Pentium III 1 GHz unter Linux die ersten 81 Primzahlen von 2 bis 419 (Ergebnis siehe unten).
Dabei stellen sich mir zwei Fragen:
1. Für welche Startzahlen werden Primzahlen generiert, außer für 2? Mit 123 als Startwert z.B. kommen sehr schöne symmetrische Muster heraus, wenn man sich die Zahlenfolge anschaut, aber keine einzige Zahl (zumindest soweit ich das getestet habe), die die Bedingung 2^p=i erfüllt.
2. Bricht der Test für ein erfolgreiches Produkt bei Primzahlen immer beim neunten Bruch ab? Bei den ersten 81 Primzahlen war das zumindest der Fall.
| Anzahl Durchläufe | Wert von i |
|---|---|
| 19 | 2^2 |
| 69 | 2^3 |
| 281 | 2^5 |
| 710 | 2^7 |
| 2375 | 2^11 |
| 3893 | 2^13 |
| 8102 | 2^17 |
| 11361 | 2^19 |
| 19268 | 2^23 |
| 36981 | 2^29 |
| 45680 | 2^31 |
| 75417 | 2^37 |
| 101354 | 2^41 |
| 118093 | 2^43 |
| 152344 | 2^47 |
| 215797 | 2^53 |
| 293897 | 2^59 |
| 327571 | 2^61 |
| 429229 | 2^67 |
| 508284 | 2^71 |
| 556494 | 2^73 |
| 701008 | 2^79 |
| 809381 | 2^83 |
| 990746 | 2^89 |
| 1274952 | 2^97 |
| 1435957 | 2^101 |
| 1531854 | 2^103 |
| 1712701 | 2^107 |
| 1820085 | 2^109 |
| 2021938 | 2^113 |
| 2835628 | 2^127 |
| 3107393 | 2^131 |
| 3549288 | 2^137 |
| 3723821 | 2^139 |
| 4553243 | 2^149 |
| 4759180 | 2^151 |
| 5333781 | 2^157 |
| 5962621 | 2^163 |
| 6405332 | 2^167 |
| 7125263 | 2^173 |
| 7873555 | 2^179 |
| 8169349 | 2^181 |
| 9547816 | 2^191 |
| 9884088 | 2^193 |
| 10500957 | 2^197 |
| 10858438 | 2^199 |
| 12878703 | 2^211 |
| 15145098 | 2^223 |
| 15964927 | 2^227 |
| 16438193 | 2^229 |
| 17302072 | 2^233 |
| 18642576 | 2^239 |
| 19166704 | 2^241 |
| 21574441 | 2^251 |
| 23168346 | 2^257 |
| 24816902 | 2^263 |
| 26517785 | 2^269 |
| 27180382 | 2^271 |
| 28985491 | 2^277 |
| 30243252 | 2^281 |
| 30965775 | 2^283 |
| 34298123 | 2^293 |
| 39319235 | 2^307 |
| 40860608 | 2^311 |
| 41744304 | 2^313 |
| 43345859 | 2^317 |
| 49278023 | 2^331 |
| 51955472 | 2^337 |
| 56624127 | 2^347 |
| 57722603 | 2^349 |
| 59709448 | 2^353 |
| 62748534 | 2^359 |
| 67060172 | 2^367 |
| 70390723 | 2^373 |
| 73886467 | 2^379 |
| 76226052 | 2^383 |
| 79796905 | 2^389 |
| 84842139 | 2^397 |
| 87407216 | 2^401 |
| 92855430 | 2^409 |
| 99574475 | 2^419 |