Wären Sie gerne Millionär? Um sich diesen Traum zu erfüllen, gibt es mehrere Möglichkeiten. Sie könnten zum Beispiel Gast bei einer TV-Sendung sein und 15 unvorhersehbare Fragen von Günther Jauch richtig beantworten. Oder Sie könnten versuchen, die Antwort auf eine einzige Frage zu finden: Wie sind die Primzahlen auf dem Zahlenstrahl verteilt? Damit hätten Sie die so genannte riemannsche Vermutung gelöst, eines von sieben »Millennium-Problemen«, deren Lösung mit je einer Million US-Dollar belohnt wird.

Und tatsächlich ist die riemannsche Vermutung nicht die einzige wichtige mathematische Fragestellung, die mit Primzahlen zusammenhängt, es gibt noch etliche weitere. Zum Beispiel, die goldbachsche Vermutung, die besagt, dass sich jede gerade Zahl, die größer ist als zwei, sich durch die Summe zweier Primzahlen ausdrücken lässt (4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5 und so weiter). Deren Beilegung wird zwar nicht mit einer Million Dollar oder Euro belohnt, aber immerhin mit Ruhm und Ehre (in der Mathe-Community). Dass es noch immer so viele Rätsel um Primzahlen gibt, erscheint erstaunlich – schließlich gibt es mehrere exakte Formeln, mit denen sich Primzahlen berechnen lassen.

Ein Beispiel für einen solchen »Primzahlgenerator« ist die Formel von Willans. Dabei handelt es sich um eine Funktion p(n), die für jeden beliebigen Wert von n die n-te Primzahl ausspuckt. Zum Beispiel: Für n = 5 liefert sie p(5) = 11, da elf die fünfte Primzahl ist. Damit sind doch alle Geheimnisse um Primzahlen gelüftet, oder? Wie sich herausstellt, stimmt das leider nicht ganz.

Die Idee hinter Willans' Formel besteht darin, zunächst eine Funktion zu finden, die Primzahlen detektiert. Sprich: Wenn man die Funktion f(x) mit einer Primzahl p füttert, soll 1 herauskommen, ansonsten 0: f(p) = 1, f(x≠p) = 0. Hat man eine solche Funktion gefunden, kann man überlegen, wie sich ein solcher Primzahldetektor in einen Primzahlgenerator umwandeln lässt. Dafür geht man zunächst davon aus, man hätte den Detektor f(x) schon gefunden.

Wie baut man aus einem Detektor einen Generator?

Mit Hilfe eines Detektors kann man auf die Anzahl der Primzahlen innerhalb eines Zahlenintervalls schließen. Summiert man die Werte f(1) + f(2) + f(3) + … + f(10), erhält man als Ergebnis die Anzahl aller Primzahlen zwischen 0 und 10, also vier (2, 3, 5, 7). Die einzelnen Summanden über f kann man sich genauer anschauen:

f(1) = 0,
f(1) + f(2) = 1,
f(1) + f(2) + f(3) = 2,
f(1) + f(2) + f(3) + f(4) = 2,
f(1) + f(2) + f(3) + f(4) + f(5) = 3,
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) = 3,
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 4…

Hier lässt sich bereits ein Muster erkennen. Möchte man die vierte Primzahl bestimmen, muss man die kleinste Zahl x finden, für die die Summe f(1) + f(2) + … + f(x) = 4 ergibt. Im obigen Beispiel ist x = 7. Dieses Prinzip lässt sich verallgemeinern: Die n-te Primzahl ist die kleinste natürliche Zahl x, für die f(1) + f(2) + … + f(x) = n. Wenn es nun gelingt, dieses Vorgehen durch eine Funktion auszudrücken, die den gesuchten Wert x liefert, hat man schon aus einem Primzahldetektor einen Generator gemacht.

Dafür ist es zunächst hilfreich, eine weitere Hilfsfunktion g(x) einzuführen, die der Summe f(1) + … + f(x) entspricht. Also:

g(1) = f(1) = 0,
g(2) = f(1) + f(2) = 1,
g(3) = f(1) + f(2) + f(3) = 2,
g(4) = f(1) + f(2) + f(3) + f(4) = 2,
g(5) = f(1) + f(2) + f(3) + f(4) + f(5) = 3,
g(6) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) = 3,
g(7) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 4 …

Um die vierte (oder allgemein: die n-te) Primzahl zu finden, muss man zählen, wie viele Werte es von x gibt, für die g(x) kleiner ist als vier (beziehungsweise n). Auf diese Weise erhält man den Wert der gesuchten vierten (oder n-ten) Primzahl. Und tatsächlich findet sich eine Funktion, die genau das zuvor Beschriebene macht – nicht erschrecken, sie sieht auf den ersten Blick etwas kompliziert aus, ist aber ganz harmlos:

\[ \sum_{i=1}^{2^n} \left\lfloor \left(\frac{n}{g(i)+1}\right)^{\frac{1}{n}}\right\rfloor +1 \]

Wir arbeiten uns Schritt für Schritt vor. Die eckigen Klammern \(\lfloor\) und \(\rfloor\) geben an, dass man den Wert in ihrem Inneren abrunden muss. Also ist \(\lfloor 1{,}7\rfloor= 1\), ebenso wie \(\lfloor 1{,}1211116546\rfloor= 1\). Der Term innerhalb der eckigen Klammern, \( \left(\frac{n}{g(i)+1}\right)^{\frac{1}{n}}\), scheint schon etwas komplizierter. Um diesen besser zu verstehen, kann man sich den dazugehörigen Graphen ansehen, der sich für einen festen Wert i = 4 und die Variable n ergibt:

Unabhängig davon, wie groß oder klein n ist, nimmt die Funktion \( \left(\frac{n}{g(i)+1}\right)^{\frac{1}{n}}\) entweder Werte zwischen 0 und 1 oder zwischen 1 und 2 an. Durch die umgebenden eckigen Abrundungsklammern liefert der Ausdruck also entweder eine 0 oder eine 1. Tatsächlich kommt immer 1 heraus, so lange g(i) kleiner ist als n; sobald g(i) hingegen gleich n ist oder n übersteigt, kommt 0 heraus. Die äußere Summe dient nur dazu, die Beiträge zu summieren.

Wenn man die Formel also für n = 4 auswertet, um die vierte Primzahl zu erhalten, kommt folgendes heraus:

\[ \sum_{i=1}^{16} \left\lfloor \left(\frac{4}{g(i)+1}\right)^{\frac{1}{4}}\right\rfloor +1 = 1+ 1 + 1+ 1 + 1 + 1 + 0 + … + 0 + 1 = 7 \]

Das funktioniert nicht nur für n = 4, sondern für jedes n. Durch diese Formel kann man sich stets die n-te Primzahl ausgeben lassen. Aber: Bisher habe ich eine Information unterschlagen. Ganz am Anfang habe ich angenommen, dass es einen Primzahldetektor f gibt – ohne Ihnen jedoch zu sagen, wie dieser aussieht oder funktioniert. Auch hierbei handelt es sich um eine griffige Formel, die auf den ersten Blick abschreckend wirkt, aber in Wirklichkeit gar nicht so kompliziert ist:

\[f(x)= \left\lfloor \cos^2\left(\pi \frac{(x-1)!+1}{x}\right)\right\rfloor \]

Die eckigen Abrundungsklammern kennen wir ja jetzt schon. Da der quadrierte Kosinus bloß Werte zwischen 0 und 1 liefert, garantiert das schon mal, dass f(x) bloß 0 oder 1 sein kann – wie es von einem Detektor gewünscht ist. Aber für welche Werte von x wird f(x) = 0 und für welche 1? Dafür muss man das Argument der Kosinusfunktion betrachten: \(\pi\frac{(x-1)!+1}{x}\). Das Ausrufezeichen bezeichnet eine Rechenoperation, die als »Fakultät« bekannt ist und die alle natürlichen Zahlen bis zur Zahl vor der Fakultät miteinander multipliziert. So ist: 5! = 1 · 2 · 3 · 4 · 5 = 120. Wenn man nun verschiedene Werte für x einsetzt und den Bruch \(\pi\frac{(x-1)!+1}{x}\) auswertet, erhält man folgende Ergebnisse:

Fällt Ihnen etwas auf? Falls x eine Primzahl ist, ist das Ergebnis ein ganzzahliges Vielfaches von π, ansonsten nicht. Dass das für alle Werte von x gilt, hat Joseph Louis Lagrange im Jahr 1771 bewiesen, die Tatsache ist aber als »Satz von Wilson« bekannt. Der Mathematiker John Wilson hatte diesen Zusammenhang im 18. Jahrhundert als Vermutung zwar hervorgebracht – aber nicht als Erster. Tatsächlich hatte bereits der Gelehrte Alhazen um das Jahr 1000 eine entsprechende Vermutung formuliert, die jedoch in Vergessenheit geriet.

Die Million bleibt leider aus

Der Satz von Wilson lässt sich zum Bau eines Detektors nutzen: Denn der Kosinus eines ganzzahligen Vielfachen von π ergibt stets 1 oder -1, während alle anderen Argumente der Kosinusfunktion hingegen ein Ergebnis kleiner als 1 liefern. Damit ist der Primzahldetektor fertig. Indem man die quadrierte Kosinusfunktion abrundet (durch die eckigen Klammern), liefert f(x) wie gewünscht den Wert 1, falls x eine Primzahl ist, und sonst 0.

Indem man alle bisher gewonnen Informationen zusammenfügt, lässt sich eine praktische Formel zur Berechnung von Primzahlen angeben:

\[p_n = 1+ \sum_{i=1}^{2^n} \left\lfloor \left(\frac{n}{\sum_{j=1}^i \left\lfloor \cos^2\left(\pi \frac{(j-1)!+1}{j}\right)\right\rfloor}\right)^{\frac{1}{n}}\right\rfloor \]

Versuchen Sie es gerne selbst. Wenn Sie die fünfte Primzahl berechnen wollen, müssen Sie bloß n = 5 in die Formel einsetzen und erhalten dann das korrekte Ergebnis, nämlich elf. Tatsächlich wurde diese Gleichung bereits 1964 von einem gewissen C. P. Willans veröffentlicht. Wer genau Willans ist, lässt sich nicht sagen. Es sind auch keine weiteren Fachartikel von ihm bekannt. Aber Willans wurde durch seine Formel wohl kein Millionär – nicht nur, weil es die Millennium-Preise zur Zeit seiner Veröffentlichung noch nicht gab, sondern auch, weil die Formel keine Hilfe dabei ist, irgendeine der mit Primzahlen verbundenen mathematischen Fragen zu beantworten.

Das Hauptproblem an der Gleichung haben Sie sicherlich schon selbst bemerkt, falls Sie wirklich versucht haben, sie zu nutzen: Die Berechnungen sind ziemlich aufwändig. Selbst Computern fällt es schwer, die Formel auszuwerten – insbesondere für große n. Das liegt unter anderem an der Fakultät: Die Werte werden schnell extrem groß und Berechnungen mit ihnen erfordern viel Rechenleistung.

Würde man damit extrem große Primzahlen berechnen wollen, würde man jeden Supercomputer der Welt überfordern. Um wirklich Millionär zu werden, muss man also einen anderen Weg einschlagen. Vielleicht ist es ja doch einfacher, sich zu Günther Jauch ins Studio zu setzen?