Primzahlen sind faszinierend. Sie sind die Atome, aus denen alle natürlichen Zahlen zusammengesetzt sind. Warum ist es so schwer (aufwendig), mit Sicherheit zu sagen, ob eine beliebige Zahl eine Primzahl ist, und noch viel schwieriger, im negativen Fall die Zahl in ihre Faktoren zu zerlegen?
Viele Fragen tauchen im Zusammenhang mit Primzahlen auf, und viele davon sind noch nicht geklärt. In manchen Fällen kann man noch nicht einmal etwas vermuten, da es an Beispielen mangelt. Interessanterweise kann aber jeder Laie, der über einen Computer mit Internetzugang verfügt, dabei mithelfen, das vorliegende Datenmaterial zu erweitern. Einige Hinweise dazu in den Links am Ende der Seite.
Unter den Programmen, die ich geschrieben habe, waren schon welche, die sich mit Primzahlen (z.B. Suche nach besonders großen oder solchen mit speziellen Eigenschaften), befreundeten Zahlen, Golomb-Linealen, Naturkonstanten (z.B. Pi) usw. beschäftigt haben.
Seit Spätjahr 1996 laufen auf meinen Rechnern zahlentheoretische Programme, die jeden verfügbaren CPU-Zyklus schlucken. Es versteht sich von selbst, daß meine Rechner - nicht nur deshalb - rund um die Uhr laufen.
Kern meiner Programme ist eine effiziente Primzahltest- bzw. Faktorisierfunktion. Obwohl wahrscheinlich nicht optimal, kann sie Zahlen mit bis zu 70 Stellen in vernünftiger Zeit behandeln. Ihre Strategie kann man etwa so beschreiben:
Die naive Methode, eine Zahl in Faktoren zu zerlegen (Division) ist viel zu langsam für Zahlen mit mehr als 12 Ziffern. Es gibt eine Reihe von Primzahltestverfahren und Faktorisierungsalgorithmen, die besser sind, aber unter bestimmten Bedingungen kein Ergebnis liefern, insbesondere, wenn man eine Obergrenze für den Rechenaufwand setzt.
Interessant ist nun, daß viele Verfahren zum Primzahltest die Faktorisierung von bestimmten Zahlen voraussetzen, und die Verfahren zur Faktorisierung effiziente Primzahltests (z.B. für die gefundenen Faktoren) benötigen. Es entstehen also wechselseitig rekursive Aufrufe. Glücklicherweise werden die bearbeiteten Zahlen mit jedem Aufruf um mindestens Faktor 2 kleiner, so daß die Rekursion irgendwann endet :-)
Daher kombiniert meine Funktion verschiedene dieser Verfahren derart, daß im Lauf der Berechnung gewonnene Informationen in den nächsten Schritt mit einfließen. Schaltet man einen Trace-Level > 0 ein, so kann man wie in diesem Beispiel genau verfolgen, wie die Funktion arbeitet. Das Beispiel zerlegt die Carmichael-Zahl 999905550669144001 korrekt in ihre drei Faktoren 264559, 529117 und 7143067, wobei eine Obergrenze für direkte Divisionen von nur 100 verwendet wird. Mit einer höheren Obergrenze (maximal 10 Millionen) wäre die Rekursion geringer ausgefallen.
Meine Programme laufen seit Monaten ohne Fehler, können also durchaus als stabil gelten. Zudem ist eine gewisse Absicherung gegen Rechenfehler (Pentium ;-) eingebaut.
Im Dezember 1999 entdeckte ich, daß ich meine Programme durch Änderung einer Konstanten erheblich beschleunigen konnte. Dies enhüllte völlig unerwartet (wie konnte ich nur so naiv sein?) einige Bugs in meinen Programmen. Glücklicherweise war ich durch Assertions vor falschen Resultaten geschützt. Nach etwas Debugging konnte ich den Code verbessern, und nun läuft wieder alles bestens.
Zwischen dem 16. und 23. Januar 2000 entdeckte ich ein Paar von Befreundeten Zahlen, das bisher noch unbekannt war. Es lautet:
1640320645088 = 2^5*59*199*4365899 1660299754912 = 2^5*269*349*419*1319
Das Erstaunliche an diesem Paar ist, daß manche Leute dachten, alle Befreundeten Zahlen im Bereich 1012 bis 1013 seien schon bekannt.
Ende Januar 2000 entdeckte ich eine Viererkette von Befreundeten Zahlen, die bisher noch unbekannt war. Sie lautet:
1420500714850 = 2*5^2*7*109*37234619 1626780585950 = 2*5^2*13*43*89*653969 1745036416450 = 2*5^2*683*1187*43049 1508297544350 = 2*5^2*29*109*9543167
Am 13. Februar 2000 konnte ich die Performance meiner Programme nochmals um 50% steigern, indem ich einen besseren Primzahltest für "kleine" Zahlen (kleiner als 1012) implementierte. Seit dieser Zeit werden auch alle Entdeckungen mit einem genauen Zeitstempel versehen.
Am 16. Oktober 2003 entdeckte ich eine weitere Viererkette von Befreundeten Zahlen, die bisher noch unbekannt war. Sie lautet:
741158497112 = 2^3*11*71*79*1501561 815660984488 = 2^3*7*53*274818391 965162195672 = 2^3*1637*4481*16447 846136631848 = 2^3*2011*52594271
Das Lustige daran ist, daß ich erst am 30. Juni 2004 merkte, daß ich diese Sequenz entdeckt hatte. So lange hatte ich die Logdatei nicht überprüft!