Es ist sehr einfach zu sagen, was eine Primzahl ist: eine natürliche Zahl, die nur durch 1 und sich selbst teilbar ist. Dagegen erweckt ihre Verteilung den Anschein völliger Regellosigkeit. Man kann allgemein einer Zahl durch kein einfaches Merkmal ansehen, ob sie prim ist oder nicht. Diese Diskrepanz ist bis heute Anlaß intensiver Versuche, eben doch Regelhaftigkeiten im scheinbar Regellosen zu finden – etwa durch intensives Probieren mit dem Computer (vergleiche Spektrum der Wissenschaft, September 1988, Seite 62). Die Folge der Primzahlen hört nie auf, was man mit einem eleganten, dem antiken Mathematiker Euklid zugeschriebenen Widerspruchsbeweis zeigen kann. Die größte zur Zeit bekannte Primzahl ist 2⁸⁵⁹⁴³³-1, eine gigantische Zahl mit 258716 Stellen. (Aktuelles zum Stand der Primzahlforschung, insbesondere die vollständige Dezimaldarstellung der genannten Zahl, findet man im World Wide Web unter http://www.utm.edu/research/primes/largest.html.) Es gibt also unendlich viele Primzahlen; aber je größer sie sind, um so dünner sind sie unter den natürlichen Zahlen gesät. Insbesondere kann die Lücke zwischen einer Primzahl und der nächsten beliebig groß werden. Denn zu jeder noch so großen Zahl n, die man sich ausdenken mag, läßt sich eine Folge von n zerlegbaren Zahlen angeben: alle von (n+1)!+2 bis (n+1)! +(n+1).

Primzahlzwillinge Die Abstände zwischen aufeinanderfolgenden Primzahlen werden auch im Durchschnitt immer größer. Gibt es ab einer gewissen Größe überhaupt noch Primzahlen, die dicht beieinander liegen? Paare von Primzahlen mit Abstand 2 heißen Primzahlzwillinge. Ihre Folge beginnt mit (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), ... Das bislang größte bekannte Paar besteht aus den 11713-stelligen Zahlen 242206083×2³⁸⁸⁸⁰ ±1; Karl-Heinz Indlekofer und Antal Jarai von der Universität Paderborn haben damit im November 1995 einen Rekord von Harvey Dubner (mit 5129 Stellen) überboten, der nur einen Monat lang Bestand hatte. Es sieht zunächst so aus, als seien sehr viele Primzahlen Angehörige eines Zwillingspaars. Tatsächlich nimmt jedoch deren Häufigkeit noch erheblich schneller ab als die der Primzahlen selbst. So gehören von den 25 Primzahlen bis 100 noch 15 zu einem Zwillingspaar, von den 168 Primzahlen unter 1000 nur noch 69. Genaueres über die Abnahme der Häufigkeit auszusagen ist aber äußerst schwierig. Für die Anzahl aller Primzahlen unterhalb einer gegebenen Schranke gibt es eine Näherungsformel, die um so genauer wird, je größer die Schranke ist (Spektrum der Wissenschaft, April 1993, Seite 11): eine asymptotische Formel. Eine entsprechende Aussage für Primzahlzwillinge ist bis heute nicht bewiesen. Bereits die Frage, ob es überhaupt unendlich viele Primzahlzwillinge gibt, stellte sich als außerordentlich schwierig heraus. Der Zahlentheoretiker Edmund Landau (1877 bis 1938) schrieb 1927 dazu: "Die Mittel der Zahlentheorie und der Analysis sind bis heute nicht kräftig genug, um diese Frage zu beantworten (man würde wohl auf ja wetten)." Das gilt bis heute. Immerhin fanden 1923 die britischen Mathematiker Godfrey Harold Hardy (1877 bis 1947) und John Edensor Littlewood (1885 bis 1977) als Folgerung aus einer viel allgemeineren Arbeit gute Gründe für eine erheblich weitergehende Vermutung. Für die Anzahl PI2(x) der Primzahlzwillinge unterhalb von x sollte die asymptotische Formel ((Formel 1)) gelten. (Das Symbol log bezeichnet den natürlichen Logarithmus.) Die zunächst durch eine Formel definierte Konstante c₂ wurde 1961 auf 42 Stellen genau berechnet: c₂=0,660161815846869.... Wenn die (bis heute nicht bewiesene) Vermutung von Hardy und Littlewood zutrifft, gibt es unendlich viele Primzahlzwillinge, und die Wahrscheinlichkeit, daß eine beliebige Primzahl p eine Zwillingsschwester p+2 hat, ist ungefähr gleich 2c₂/log₂ p. Ob eine Zahlenfolge mehr oder weniger dünn gesät ist, dafür gibt es ein eher indirektes, wenngleich hilfreiches Kriterium. Wenn man die Kehrwerte aller natürlichen Zahlen aufsummiert, strebt die entsprechende Summe 1+1/2+1/3 +1/4+... gegen unendlich. Nimmt man statt dessen eine dünn gesäte Zahlenfolge, etwa die der Zweierpotenzen 1, 2, 4, 8, 16, ... oder der Quadratzahlen 1, 4, 9, 16, 25, ..., so bleibt die Summe der Kehrwerte beschränkt: Sie konvergiert, das heißt, sie strebt einem endlichen Grenzwert zu. Gleiches gilt auch für Folgen, die auf den ersten Blick alles andere als dünn gesät anmuten: Für die Folge n^q (für q=2 ist das die Folge der Quadratzahlen, für q=1 die aller natürlichen Zahlen), geeignet auf ganzzahlige Werte gerundet, konvergiert die Summe der Kehrwerte selbst dann, wenn q nur eine Winzigkeit größer als 1 und die Folge selbst von derjenigen aller natürlichen Zahlen zunächst nicht zu unterscheiden ist. Es kommt nicht auf die ersten Glieder der Folge an, sondern auf ihr Verhalten im Unendlichen. Überraschenderweise ist die Folge der Primzahlen in diesem Sinne nicht dünn gesät, wie Leonhard Euler (1707 bis 1783) bereits 1737 gezeigt hat, die Folge der Primzahlzwillinge dagegen sehr wohl: Der norwegische Mathematiker Viggo Brun (1885 bis 1978) hat 1919 bewiesen, daß die Summe ((Formel 2)) einem Grenzwert zustrebt. Die exakte Größe dieser Zahl, die mittlerweile Brunsche Konstante heißt und allgemein mit B bezeichnet wird, ist bis heute nicht bekannt. Wenn man die Vermutung von Hardy und Littlewood als richtig unterstellt, kann man aus den Ergebnissen von Zählungen einen Wert von B=1,90216 extrapolieren (Bild 2).
Zählungen von Primzahlzwillingen

Die ersten größeren, heute noch bekannten Tabellen von Primzahlen entstanden im 17. Jahrhundert. Frans van Schoten (1615 bis 1660) berechnete 1657 eine Tabelle aller Primzahlen bis 10000. Leonhard Euler wies in seinem Werk "Vollständige Anleitung zur niedern und höheren Algebra" in einer Fußnote auf die Existenz einer Tabelle sämtlicher Primzahlen bis 100999 hin, die Peter Jäger, Roßschreiber und Quartiermeister zu Nürnberg, 1746 erstellt habe. Die erste bedeutende Zählung von Zwillingen hat dann 1878 der Brite James W. L. Glaisher (1848 bis 1928) unternommen; er durchsuchte systematisch das Intervall von 1 bis 100000 sowie fünf weitere, ebenso lange Intervalle beginnend bei einer, zwei, sechs, sieben und acht Millionen. Um die Vermutung von Hardy und Littlewood zu überprüfen, zählte Frau G. A. Streatfeild 1923 sämtliche Primzahlzwillinge bis 1000000 durch. Der Vergleich der aus der Formel berechneten Werte mit der tatsächlichen Anzahl ergab eine beeindruckende Übereinstimmung (Bild 1). Mit dem Einzug elektronischer Rechenmaschinen konnte man einerseits feststellen, daß die bisherigen, sämtlich mit Bleistift und Papier durchgeführten Berechnungen eine erstaunliche Präzision erreicht hatten, andererseits ihren Umfang weit übertreffen. Der australische Mathematiker Richard P. Brent ermittelte 1974 die Anzahl aller Primzahlzwillinge bis 10¹¹ und die Summe über ihre Kehrwerte – ein Rekord, den wir im Januar 1994 zunächst um eine Zehnerpotenz überbieten konnten. Nach einer ersten Optimierung des eingesetzten Verfahrens erreichten wir im Mai 1994 die Marke von 10¹³, womit die Grenze des Möglichen erreicht schien. Wie bestimmt man solche Anzahlen? Für Primzahlen gibt es ein Verfahren des Astronomen Ernst Daniel Friedrich Meissel (1826 bis 1895) aus dem Jahre 1870, mit dem man die Anzahl sämtlicher Primzahlen bis zu einer gewissen Schranke exakt berechnen kann, ohne vorher jede einzelne explizit bestimmen zu müssen. Im vergangenen Jahr hat Marc Deleglise an der Universität Lyon mit einer Weiterentwicklung dieses Algorithmus die Anzahl aller Primzahlen bis 10¹⁸ berechnet. Leider ist für Primzahlzwillinge kein vergleichbares Verfahren bekannt. Es bleibt also nichts anderes übrig, als mit dem seit der Antike bekannten Sieb des Eratosthenes (Spektrum der Wissenschaft, September 1988, Seite 8) alle Primzahlen in dem interessierenden Bereich zu bestimmen und in einem zweiten Schritt daraufhin zu überprüfen, ob sie eine Zwillingsschwester haben. Siebverfahren sind in verschiedenen Bereichen innerhalb der Zahlentheorie mächtige Werkzeuge (Spektrum der Wissenschaft, Oktober 1993, Seite 22). Für Berechnungen von PI2(x), wenn die Zahl x in der Größenordnung 10¹³ liegt, muß das Verfahren in bezug auf Speicherplatz- und Zeitbedarf verbessert werden. In der Urform streicht man aus einer Tabelle sämtlicher Zahlen bis (beispielsweise) 10¹³ nacheinander alle Vielfachen der Primzahlen unterhalb von SQRT(10¹³) heraus. Das geht sehr schnell, wenn die komplette Tabelle im Hauptspeicher gehalten wird; aber deren Umfang übersteigt heutige übliche Speichergrößen immer noch bei weitem. Der Zeitbedarf des klassischen Siebverfahrens hat die Größenordnung O(x × log log x). Diese Notation (gesprochen "O von x...", nicht "Null von x...") drückt aus, daß die Zeit zur Bestimmung aller Primzahlen bis x im schlimmsten Falle proportional zu x × log log x ist; eine Proportionalitätskonstante pflegt man nicht hinzuschreiben, da sie ohnehin von technischen Einzelheiten des verwendeten Rechners abhängig ist. Für x=10¹³ wäre also eine Folge weniger Rechenschritte ungefähr 30×10¹³ mal auszuführen – selbst für einen Supercomputer ein immenser Aufwand. Glücklicherweise eignet sich das Siebverfahren zur Parallelisierung: Man zerlege die große Tabelle in zahlreiche Untertabellen und vertraue jede einem Prozessor innerhalb eines großen Parallelrechners an. Die Kommunikation unter den Prozessoren hält sich in engen Grenzen, weil die einzelnen Teiltabellen weitgehend unabhängig voneinander bearbeitet werden können. Jonathan Sorenson von der Universität von Wisconsin in Madison und Ian Parberry von der Universität von Nord-Texas in Denton haben zwei schnelle parallele Primzahlsiebe vorgeschlagen, die nur noch O(logx) beziehungsweise O(SQRT(x)) Zeit benötigen. Allerdings braucht man dafür – der gesamte Arbeitsaufwand wird ja nicht weniger – unbezahlbar hohe Anzahlen von Prozessoren: O(x×loglogx/logx) beziehungsweise O(SQRT(x)) Stück. Für x=10¹³ würde das bedeuten, daß 10¹² Prozessoren in ungefähr 30 Zeiteinheiten, drei Millionen Prozessoren in ungefähr drei Millionen Zeiteinheiten fertig wären. Unsere Parallelisierung arbeitet mit deutlich weniger Prozessoren um den Preis entsprechend längerer Rechenzeit. Wir halten die Anzahl der Prozessoren und die Größe der Teiltabellen variabel, so daß wir Computer der verschiedensten Größenklassen einschließlich massiv paralleler Rechner einsetzen können. Das Verfahren beruht auf dem sogenannten Farmer-Worker-Prinzip (vergleiche Spektrum der Wissenschaft, Oktober 1989, Seite 64): Ein Prozeß (der Farmer oder Aufseher) koordiniert die Aufteilung des Intervalls und vergibt Teilprobleme an die Arbeitsprozesse (die Workers), die ihrerseits (Zwischen-)Ergebnisse an den Farmer senden. Für einen möglichst geringen Kommunikationsaufwand erwies es sich als günstig, wenn jeder Prozessor eine Tabelle mit allen Primzahlen von 1 bis SQRT(x), deren Vielfache gestrichen werden müssen, im lokalen Hauptspeicher hält; für x=10¹⁴ erfordert das weniger als 700 Kilobyte Speicherplatz. Insgesamt haben wir unser Verfahren auf fünf verschiedenen Rechnertypen eingesetzt, darunter auch zwei transputerbasierten Mehrprozessorsystemen. Diese brauchen keinen globalen Speicher mehr; die Kommunikation unter den Prozessoren ist durch spezielle Hardware – sogenannte Links – von der eigentlichen Rechenarbeit abgekoppelt. Die nach William of Occam, einem englischen Philosophen aus dem 14. Jahrhundert, benannte Programmiersprache OCCAM2 stellt eine nahezu ideale Möglichkeit zur Verfügung, die erwähnten Ressourcen zu nutzen. Es ist uns bisher mit bis zu 50 parallelen Prozessoren gelungen, PI2(10<sup>14SUP>)=135780321665 zu berechnen. Die Summe der Kehrwerte B(1014) ist 1,820244968130, woraus sich für die Brunsche Konstante der Schätzwert 1,902160577783 ergibt. Damit sind wir tausendmal so weit vorgedrungen wie Richard P. Brent, und es ist (in doppeltem Sinne) noch immer kein Ende in Sicht.


Aus: Spektrum der Wissenschaft 2 / 1996, Seite 26
© Spektrum der Wissenschaft Verlagsgesellschaft mbH</sup>