Eine Funktion, die zählt
Wir brauchen eine Schreibweise für das, was wir an Abend 2 von Hand gezählt haben. Man schreibt
π(x) = Anzahl der Primzahlen, die kleiner oder gleich x sind
Das π hat nichts mit dem Kreis zu tun — es ist der griechische Anfangsbuchstabe von prímos. Gelesen wird es „pi von x".
Aus Abend 2 wissen wir bereits π(100) = 25. Und weiter:
| x | π(x) | Anteil |
|---|---|---|
| 10 | 4 | 40,00 % |
| 100 | 25 | 25,00 % |
| 1 000 | 168 | 16,80 % |
| 10 000 | 1 229 | 12,29 % |
| 100 000 | 9 592 | 9,59 % |
| 1 000 000 | 78 498 | 7,85 % |
| 10 000 000 | 664 579 | 6,65 % |
| 100 000 000 | 5 761 455 | 5,76 % |
Jede Zeile hat die zehnfache Spanne der vorigen — der Anteil sinkt aber nicht auf ein Zehntel, sondern nur um etwa ein Fünftel. Die Primzahlen werden dünner, aber sehr gemächlich.
Das Muster
Sehen wir uns die Kehrwerte an. Bei 1 000 ist etwa jede sechste Zahl prim, bei einer Million etwa jede dreizehnte, bei hundert Millionen etwa jede siebzehnte.
Die Folge 6, 13, 17 … erinnert an etwas. Rechnen wir den natürlichen Logarithmus:
ln(1 000) ≈ 6,9
ln(1 000 000) ≈ 13,8
ln(100 000 000) ≈ 18,4
Das ist der Fund. Der Abstand zwischen Primzahlen entspricht in der Nähe von x etwa dem natürlichen Logarithmus von x. Oder umgekehrt ausgedrückt:
Primzahlsatz: π(x) verhält sich für große x wie x / ln(x).
Gauß vermutete das mit 15 Jahren beim Betrachten von Primzahltabellen. Bewiesen wurde es erst rund hundert Jahre später, 1896, unabhängig von Hadamard und de la Vallée Poussin.
Wie gut ist die Näherung?
| x | π(x) | x / ln x | Abweichung |
|---|---|---|---|
| 1 000 | 168 | 145 | 14 % zu klein |
| 1 000 000 | 78 498 | 72 382 | 8 % zu klein |
| 100 000 000 | 5 761 455 | 5 428 681 | 6 % zu klein |
Die Näherung trifft die Größenordnung, liegt aber beharrlich zu niedrig. Es gibt eine deutlich bessere, den Integrallogarithmus Li(x). Für 1 000 liefert er rund 178 statt 145 — bei einem wahren Wert von 168.
Der Unterschied zwischen π(x) und Li(x) ist kein Schönheitsfehler. Er ist das eigentliche Thema. Wie groß dieser Fehler höchstens werden kann, ist genau die Frage der Riemannschen Vermutung — davon an Abend 6 mehr.
Die Frage des Abends
Jetzt können wir die Leitfrage beantworten. Wir drehen die Sache um: Nicht „wie viele Primzahlen gibt es bis x", sondern „ab welchem x liegt der Anteil unter einer bestimmten Schwelle".
Bis 10 000 ist der Anteil noch 12,29 %, bis 100 000 nur noch 9,59 %. Irgendwo dazwischen fällt er unter 10 %. Nachgerechnet ergibt sich:
Ab 64 721 bleibt der Anteil der Primzahlen dauerhaft unter 10 %.
„Dauerhaft" ist wichtig. Der Anteil fällt nicht gleichmäßig; bei jeder neuen Primzahl springt er ein winziges Stück nach oben. Gemeint ist die Stelle, ab der er die 10 % nie wieder erreicht.
Dasselbe für andere Schwellen — diese Werte sind durch vollständiges Durchrechnen bestimmt, nicht geschätzt:
| Anteil fällt unter | ab |
|---|---|
| 25 % | 121 |
| 20 % | 361 |
| 15 % | 2 181 |
| 10 % | 64 721 |
| 8 % | 792 801 |
| 7 % | 4 692 158 |
Wo das Rechnen aufhört
Und darunter? Bei 2 %, bei 1 %, bei einem Promille?
Dort kommt man mit Durchrechnen nicht mehr hin. Kein Rechner der Welt siebt bis dorthin. Es bleibt der Primzahlsatz — und der liefert eine Näherung:
| Anteil fällt unter | ungefähr ab | Stellen |
|---|---|---|
| 2 % | 1,4 · 10²² | 23 |
| 1 % | 7,4 · 10⁴³ | 44 |
| 0,5 % | 2,0 · 10⁸⁷ | 88 |
| 1 ‰ | 5,4 · 10⁴³⁴ | 435 |
| 0,1 ‰ | 2,4 · 10⁴³⁴³ | 4 344 |
Lassen Sie die letzte Zeile wirken. Damit nur noch eine von zehntausend Zahlen prim ist, muss man zu Zahlen mit über viertausend Stellen gehen. Zum Vergleich: Die Anzahl der Atome im beobachtbaren Universum hat etwa 80 Stellen.
Die Faustregel dahinter
Rechnet man die Schwellen nicht als Zahl, sondern als Logarithmus, zeigt sich etwas Erstaunliches:
| Anteil | ln x an der Schwelle |
|---|---|
| 0,5 % = 1/200 | 201,01 |
| 1 ‰ = 1/1 000 | 1 001,00 |
| 0,1 ‰ = 1/10 000 | 10 001,00 |
Faustregel: Soll der Anteil unter 1/n fallen, liegt die Schwelle bei etwa e hoch (n + 1).
Das ist unmittelbar einsichtig, wenn man den Primzahlsatz umstellt: Der Anteil π(x)/x ist ungefähr 1/ln(x). Setzt man das gleich 1/n, kommt ln(x) ≈ n heraus — die zusätzliche 1 stammt aus der genaueren Näherung durch Li(x).
Der Anteil sinkt also gemächlich, die Zahl aber, ab der er sinkt, explodiert. Von 1 % auf 0,1 % wächst die Schwelle von 44 auf 435 Stellen.
Am Rechner
Unter Werkzeuge · Primzahldichte können Sie einen beliebigen Prozentsatz eingeben und bekommen die Schwelle. Probieren Sie 3 %, 0,2 %, 0,05 %. Darunter steht die nachgerechnete Tabelle, und daneben steht, wie weit die Näherung vom exakten Wert abweicht — bei 10 % sind es rund 6 %.
Übungen
Wie dicht liegen die Primzahlen?
1. Wie groß ist der Anteil der Primzahlen bis 1 000? Rechnen Sie ihn aus π(1 000) = 168 aus und geben Sie an, etwa jede wievielte Zahl prim ist.
2. Berechnen Sie die Näherung 1 000 / ln(1 000). Um wie viel Prozent liegt sie unter dem wahren Wert 168?
3. Schätzen Sie mit dem Primzahlsatz, wie viele Primzahlen es zwischen 1 000 000 und 1 001 000 gibt — also in einem Fenster der Breite 1 000.
4. Wie viele Primzahlen hat es laut Tabelle zwischen 10 Millionen und 100 Millionen? Wie groß ist der Anteil in diesem Bereich (nicht von 1 an gezählt)?
5. Ab welcher Zahl liegt der Anteil dauerhaft unter 10 %? Und ab welcher unter 7 %? Wie oft so groß ist die zweite Zahl?
6. Verwenden Sie die Faustregel ln(x) ≈ n + 1, um abzuschätzen, ab welcher Zahl nur noch jede fünfzigste Zahl prim ist. Geben Sie das Ergebnis als Zehnerpotenz an.
Zum Nachdenken. Jemand sagt: „Wenn die Primzahlen immer dünner werden, gibt es irgendwann einen Bereich der Länge 1 000, in dem keine einzige liegt." Hat er recht? Was haben wir an Abend 3 dazu gesehen?
Lösungen anzeigen— erst selbst rechnen lohnt sich
1. 168 / 1 000 = 16,8 %.
Der Kehrwert ist 1 000 / 168 ≈ 5,95 — also ist etwa jede sechste Zahl bis 1 000 prim.
2. ln(1 000) ≈ 6,9078, also
1 000 / 6,9078 ≈ 144,8
Abweichung: (168 − 144,8) / 168 ≈ 13,8 % zu klein.
Die Näherung ist also brauchbar, aber in diesem Bereich noch deutlich zu niedrig. Sie wird mit wachsendem x relativ besser: bei 100 Millionen liegt der Fehler nur noch bei rund 6 %.
3. In der Nähe von x liegt der Abstand zwischen zwei Primzahlen bei etwa ln(x). Für x = 1 000 000:
ln(1 000 000) ≈ 13,8
1 000 / 13,8 ≈ 72
Erwartung: etwa 72 Primzahlen. Der tatsächliche Wert liegt in dieser Größenordnung — eine Schätzung, kein exakter Wert, denn einzelne Fenster schwanken erheblich.
4. 5 761 455 − 664 579 = 5 096 876 Primzahlen.
Der Bereich ist 100 000 000 − 10 000 000 = 90 000 000 Zahlen breit. Anteil:
5 096 876 / 90 000 000 ≈ 5,66 %
Das liegt unter den 5,76 %, die für den gesamten Bereich bis 100 Millionen gelten — verständlich, denn die dichten ersten Millionen sind hier nicht mitgezählt.
5. Unter 10 % ab 64 721, unter 7 % ab 4 692 158.
4 692 158 / 64 721 ≈ 72,5
Die zweite Zahl ist also rund 72-mal so groß. Für drei Prozentpunkte weniger. Das ist die Grundbewegung dieses Abends: kleine Schritte beim Anteil, gewaltige Sprünge bei der Schwelle.
6. Jede fünfzigste heißt Anteil 1/50, also n = 50:
ln(x) ≈ 51
x ≈ e⁵¹ ≈ 1,4 · 10²²
Das ist dieselbe Zahl wie die 2-%-Schwelle aus dem Skript — kein Zufall, denn 1/50 = 2 %. Die Aufgabe prüft, ob der Zusammenhang gesehen wird.
Zum Nachdenken. Er hat recht, und wir haben es an Abend 3 sogar bewiesen.
Mit dem Fakultäts-Trick lässt sich eine Strecke beliebiger Länge ohne Primzahl konstruieren: 1 001! + 2 bis 1 001! + 1 001 sind tausend aufeinanderfolgende zusammengesetzte Zahlen.
Nur folgt das nicht daraus, dass die Primzahlen dünner werden — die beiden Aussagen haben nichts miteinander zu tun. Die Lücken gäbe es auch bei gleichbleibender Dichte. Die Begründung des Sprechers ist also falsch, obwohl seine Behauptung stimmt. Solche Fälle sind in der Mathematik die lehrreichsten.