▦ Der Prime-Block-Algorithmus

Die Idee

Das klassische Sieb des Eratosthenes streicht für jede Primzahl immer wieder dieselben Vielfachen, bei jedem neuen Zahlenbereich von vorn. Der Prime-Block-Algorithmus nutzt stattdessen eine einfache, aber mächtige Beobachtung:

Zerlegt man den Zahlenstrahl in Blöcke fester Größe B, dann gibt es für jede Primzahl p nur endlich viele verschiedene „Stempel", Bitmuster ihrer Vielfachen innerhalb eines Blocks. Wie das Muster aussieht, hängt allein davon ab, mit welchem Rest der Block relativ zu p beginnt, also der Restklasse r = Blockstart mod p.

Bei Blockgröße B = 100 hat die 7 nur 7 verschiedene Muster, die 13 nur 13 und die Basisteiler-Primzahlen 2 und 5 sogar nur ein einziges, weil sie 100 teilen (gcd = p). Nach L Blöcken wiederholt sich alles exakt. Diese Muster werden einmal berechnet, in der SQLite-Datenbank gespeichert und ab dann nur noch nachgeschlagen.

Die Variablen

B

die Blockgröße, hier 100, so viele Zahlen stehen in einem Block

p

eine Primzahl, ihre Vielfachen bilden das Muster (den Stempel)

gcd(p, B)

der größte gemeinsame Teiler von p und B

L

die Zykluslänge, L = p / gcd(p, B), so viele verschiedene Muster hat eine Primzahl, nach L Blöcken wiederholt sich die Folge

r

die Restklasse, r = Blockstart mod p, sie legt fest, wo die Vielfachen im Block liegen

n

die Blocknummer, Block n enthält die Zahlen n·B bis n·B+B−1

F

die erste Folie, im allerersten Block bleibt die Primzahl selbst prim, deshalb sind 0·p und 1·p dort nicht markiert

So funktioniert das Sieben

Der Algorithmus ist selbstfortsetzend („Never ending Primes"): Die in Block n gefundenen Primzahlen sieben die späteren Blöcke mit. Zum Sieben von Block n genügen die Primzahlen bis √(n·B+B−1) und die sind durch die vorherigen Blöcke garantiert schon alle in der Datenbank.

Interaktive Demo

Jeder Block ist ein 10×10-Raster (B = 100), gelesen von links oben nach rechts unten. Violette Zellen sind Vielfache (zusammengesetzt), helle Zellen sind Primzahlen. Violette Zellen sind Vielfache (zusammengesetzt), dunkle Zellen sind Primzahlen.

Muster-Explorer: alle Stempel einer Primzahl

Hier siehst du den vollständigen Zyklus einer Primzahl: alle L = p / gcd(p, 100) Restklassen-Muster. Nach L Blöcken wiederholt sich die Folge exakt, mehr muss nie berechnet werden. Die erste Folie F (First) ist dabei besonders: Im allerersten Block wäre das erste markierte Vielfache die Primzahl selbst, und die bleibt ja prim. Bei F sind 0·p und 1·p deshalb nicht markiert, das volle Muster der Restklasse 0 gilt erst, wenn der Zyklus das nächste Mal bei R0 ankommt.

Blöcke wachsen im Quadrat

Die Blockgröße ist nicht festgelegt: Blöcke lassen sich zum Quadrat der Blockgröße vergrößern, aus 100er-Blöcken werden 10.000er (100²), daraus 100.000.000er (10.000²) und so weiter. Ein großer Block ist dabei nichts Neues, er besteht einfach aus B kleinen Blöcken hintereinander, man muss ihn nur aufschneiden.

Die gespeicherten Stempel bleiben dabei dieselben: Das Muster eines 10.000er-Blocks für die Primzahl p besteht aus 100 aufeinanderfolgenden 100er-Mustern, deren Restklasse von Scheibe zu Scheibe um 100 mod p weiterspringt. Genau so arbeitet der Code: Er siebt große Bereiche als Folge von 100er-Scheiben und setzt sie aus den vorhandenen Mustern zusammen. In der Sprache der dynamischen Basen ist das der Wechsel von Basis b^m zu Basis b^2m, dieselbe Struktur auf der nächstgröberen Skala.

Mathematischer Hintergrund

Warum wiederholen sich die Muster? Das Muster eines Blocks hängt nur von der Restklasse r = Blockstart mod p ab. Von Block zu Block springt der Rest um B mod p weiter. Nach L = p/gcd(p,B) Schritten ist man wieder bei der Ausgangs-Restklasse, der Zyklus schließt sich. Das ist dieselbe Zyklenstruktur, die in den Papers als Bahnen einer Gruppenwirkung beschrieben wird.

Verbindung zu den dynamischen Basen: Liest man einen Block als eine Ziffer in der Basis b^m (z. B. 100 = 10²), entspricht das Sieben in Blöcken genau dem Übergang von der feinen zur groben Skala aus dem Paper Dynamic Bases and Periodic Representations of Rational Numbers: Die Blockperiode ist die Ordnung von b^m modulo p und teilt stets die klassische Periode. Periodizität ist nicht atomar, sondern hierarchisch zerlegbar.

Verbindung zum Prime Torus: Jede Primzahl p mit Periodenlänge L(p) definiert einen Torusknoten (p, L(p)), die Restklassen-Zyklen der Blöcke sind die diskreten Schritte dieser Spirale (Prime Numbers Are Never Alone).

Komplexität: Pro Primzahl p werden höchstens p Muster à B Bit gespeichert. Das Sieben eines Blocks kostet nur das Laden mehrerer Muster (eines pro Primzahl bis √N) plus eine ODER-Verknüpfung pro Muster. Bereits gesiebte Blöcke kommen vollständig aus der Datenbank.

Downloads