5. Das Sieb von Sundaram
Ein Produkt zweier natürlicher Zahlen ist genau dann ungerade, wenn beide Faktoren des Produkts ungerade sind. Aus dieser grundlegenden Eigenschaft der Multiplikation gewinnen wir folgende Einsicht über zusammengesetzte ungerade Zahlen:
Satz (Darstellung der ungeraden zusammengesetzten Zahlen)
Die zusammengesetzten ungeraden Zahlen sind genau die Zahlen der Form
u2 + k 2u
mit einer ungeraden Zahl u > 1 und einer natürlichen Zahl k ≥ 0.
In mengentheoretischer Schreibweise lautet der Satz:
{ n | n ist ungerade und nicht prim } = { u2 + k 2u | u > 1 ist ungerade, k ≥ 0 }.
Beweis
Seien zunächst u > 1 ungerade und k ≥ 0. Weiter sei n = u2 + k 2u. Dann gilt
n = u (u + 2k).
Wegen u > 1 ist n zusammengesetzt. Da u ungerade und 2k gerade ist, ist u + 2k ungerade, sodass n das Produkt zweier ungerader Zahlen und damit ungerade ist.
Sei nun umgekehrt n eine zusammengesetzte ungerade Zahl. Dann gibt es ungerade Zahlen u ≤ v mit n = u v. Sei d = v − u, sodass d ≥ 0 und
n = u v = u(u + d) = u2 + u d.
Da d ≥ 0 gerade ist, gibt es ein k ≥ 0 mit d = 2k. Folglich ist n = u2 + u 2 k, also hat n die gewünschte Form.
Aus diesem Ergebnis gewinnen wir folgendes Siebverfahren für die Primzahlen. Sei wieder n eine beliebig große Grenze. Da die 2 die einzige gerade Primzahl ist, genügt es, die ungeraden Zahlen im Intervall von 3 bis n zu betrachten.
Das Sieb von Sundaram (1934)
Sei n eine beliebige natürliche Zahl. Wir erstellen eine Liste aller ungeraden Zahlen des Intervalls von 3 bis n. Nun streichen wir der Reihe nach die Zahlen
9, 9 + 1 · 6, 9 + 2 · 6, 9 + 3 · 6, …
25, 25 + 1 · 10, 25 + 2 · 10, 25 + 3 · 10, …
49, 49 + 1· 14, 49 + 2 · 14, 49 + 3 · 14, …
…
u2, u2 + 2u, u2 + 2(2u), u2 + 3(2u), …
…
die in unserem Intervall liegen. Dabei durchläuft u alle ungeraden Zahlen mit u2 ≤ n.
Nach dem obigen Darstellungssatz werden genau die ungeraden zusammengesetzten Zahlen gestrichen, sodass genau die Primzahlen des Intervalls von 3 bis n übrigbleiben. Das Verfahren ist im Gegensatz zum Sieb des Eratosthenes nicht rekursiv, die Startpunkte
9, 25, 49, 81, …
der Streichungs-Progressionen liegen von Beginn an fest, während sich die markierten Zahlen
2, 3, 5, 7, …
bei Eratosthenes erst während der Berechnung ergeben. In der schnelleren Version ist das Sieb des Eratosthenes de facto eine verbesserte Form des Siebs von Sundaram. Denn in dieser Version streichen wir Progressionen der Form
p2, p2 + p, p2 + 2p, p2 + 3p, p2 + 4p, …, wobei p prim.
Für ungerade p (also p > 2) ist jede zweite Zahl gerade, sodass wir uns auch diese Streichungen sparen können, wodurch sich Progressionen wie bei Sundaram ergeben. Für das Intervall von 2 bis n2 werden bei Sundaram etwa n/2 Durchläufe benötigt, während das Sieb des Eratosthenes in der schnellen Version nur so viele Durchläufe benötigt, wie es Primzahlen kleinergleich n gibt (nach dem Primzahlsatz also etwa n/log(n)). Überspringen wir beim Sieb von Sundaram Progressionen mit einem Startpunkt u2, falls wir u bereits gestrichen haben (etwa für die Zahl u = 9 oder u = 15 = 9 + 6), so gelangen wir zu einer rekursiven Version, die im Wesentlichen mit dem Sieb des Eratosthenes übereinstimmt.
Klassische Darstellung des Siebs von Sundaram
Das Sieb von Sundaram wird oft so beschrieben:
(1) | Wir streichen aus einem Intervall 1, …, n alle Zahlen der Form i + j + 2ij mit 1 ≤ i ≤ j. |
(2) | Jede nichtgestrichene Zahl wird verdoppelt und um 1 erhöht. |
Die so erhaltenen Zahlen sind dann genau die Primzahlen des Intervalls 3, …, 2n + 1.
Die Äquivalenz zur obigen Version können wir so einsehen:
Seien i, j natürliche Zahlen mit 1 ≤ i ≤ j. Weiter sei k = j − i. Dann gilt
i + j + 2ij = 2i + k + 2i2 + 2ik.
Setzen wir u = 2i + 1, so gilt
2(i + j + 2ij) + 1 = 4i2 + 4i + 1 + 4ki + 2k = u2 + k2u.
Nach unserem Satz stellen also die Zahlen der Form 2(i + j + 2ij) + 1 alle zusammengesetzten ungeraden Zahlen dar. Damit sind die verdoppelten und um 1 erhöhten nicht gestrichenen Zahlen aus (1) genau die Primzahlen des Intervalls 3, …, 2n + 1.
In obiger „u2 + k2u“-Version wird das Verhältnis zum Sieb des Eratosthenes klarer, weswegen wir diese Darstellung bevorzugt haben.
Obwohl das Sieb von Sundaram letztendlich im Sieb von Eratosthenes aufgeht (und wohl deswegen keine große Beachtung fand), so stellt es doch einen neuen interessanten Ansatz dar. Es bringt eine interessante Information über die abgerundete Hälfte einer ungeraden Primzahl ans Licht. Ist n ≥ 3 ungerade, so können wir n eindeutig in der Form n = 2k + 1 schreiben. Nach den obigen Überlegungen ist n genau eine Primzahl, wenn die abgerundete Hälfte k von n nicht von der Form i + j + 2ij ist.