Sieb des Eratosthenes

Major T.O.M.

Registriertes Mitglied
Beruflich als Doktorand. :) Aber bei uns am Institut beschäftigen wir uns nur mit reiner Zeitintegration. In der Regel DAE. Aber keine PDE.

Und du? Bist du Doktorand, PostDoc oder vielleicht sogar Professor für Zahlentheorie?
 

Bernhard

Registriertes Mitglied
Beruflich als Doktorand. :)
Ok :)

Aber bei uns am Institut beschäftigen wir uns nur mit reiner Zeitintegration.
Lustigerweise habe ich zu einem vergleichbaren Thema ca. ab 1997 auch mal ca. 1,5 Jahre als Doktorand an der RWTH gearbeitet, aber dann wegen mangelhafter Ergebnisse ohne Prüfung aufgegeben. Es waren atomphysikalische Simulationen im Rahmen der Trägheitsfusion mit höchstintensiven Lasern und es ging um die Zeitentwickung von Schrödinger-Wellenfunktionen mit Hilfe von finiten Elementen, die aber komplett selbst und in C++ programmiert wurden. Mein Betreuer hatte damals auch ein paar wirklich interessante Ideen, um die Ränder des Simulationsgebietes zu berücksichtigen. Die Programmierung derselben war dementsprechend anspruchsvoll. Ich hatte damals ein kleine Bude im Zentrum von Aachen und konnte dort nicht wirklich entspannen. Gegenüber war eine große Nervenklinik und ich fand die ganze Situation insgesamt nicht wirklich motivierend.

In der Regel DAE.
Steht für?

partial differential equations.

Und du? Bist du Doktorand, PostDoc oder vielleicht sogar Professor für Zahlentheorie?
Wie oben bereits angedeutet habe ich 1994 eine Diplom-Arbeit zu den Grundlagen der Quantenmechanik in München (LMU) abgeschlossen. Meine Interessen sind also relativ breit gestreut.

Du betreibst nicht zufälligerweise einen YouTube-Kanal so a la Breaking Lab? Den Jakob schaue ich je nach Gelegenheit ganz gern.
 

Bernhard

Registriertes Mitglied
es ging um die Zeitentwickung von Schrödinger-Wellenfunktionen mit Hilfe von finiten Elementen
Genauer gesagt ein https://de.wikipedia.org/wiki/Crank-Nicolson-Verfahren, das allerdings noch mit der Invertierung einer sehr großen Matrix mit komplexen Einträgen hätte kombiniert werden müssen. Für die Matrixinvertierung hätte man nur einige Funktionen aus den numerical recipes für komplexe Zahlen erweitern müssen, was ich damals aber nicht recht erkannt hatte.

Mit dem gesamten Programmpaket hätten dann Ionisationsraten von wasserstoffähnlichen Systemen berechnet werden sollen. Es gab in diesem Umfeld einge Jahre nach mir noch eine Veröffentlichung zu diesem Thema.

In den USA wird zu dem übergeordneten Thema auch heute noch geforscht:
https://de.wikipedia.org/wiki/Trägheitsfusion
https://en.wikipedia.org/wiki/Lawrence_Livermore_National_Laboratory
https://en.wikipedia.org/wiki/National_Ignition_Facility
 
Zuletzt bearbeitet:

Bernhard

Registriertes Mitglied
Streicht man vorab die Vielfachen von 3, so erhält man nach relativ einfacher Rechnung die zwei Reihen:

6 * n + 1
6 * n + 5

wiederum mit n = 1, 2, 3, ...
Nachtrag: Die Bezeichnung Rechnung ist hier irreführend.

Es ist eher die Überlegung, dass man alle natürlichen Zahlen größer gleich 7 über die folgenden Reihen darstellen kann:

2*3*n + 1
2*3*n + 2
2*3*n + 3
2*3*n + 4
2*3*n + 5

mit n = 1,2,3....

Die zweite, dritte und vierte Reihe liefert jedoch Zahlen, die offensichtlich durch 2 bzw 3 teilbar sind. Deshalb dürfen diese beiden Reihen gestrichen werden und es bleibt nur die erste und letzte Reihe übrig. Interessant sind auch noch die Zahlen kleiner 7. Dazu formt man die letzte Reihe wie folgt um:

2*3*n + 5 = 2*3*n + 6 - 1 = 2*3*(n+1) - 1

Nun kann man die fehlende Zahl 5 auch noch darstellen und erhält die beiden Reihen:

2*3*n + 1
2*3*n - 1

mit n = 1,2,3....

Betrachtet man nun alle natürlichen Zahlen die nicht durch 2, 3 und 5 teilbar sind, macht man erneut den praktikablen Ansatz:

2*3*5*n + 1
2*3*5*n + 2
2*3*5*n + 3
2*3*5*n + 4

bis

2*3*5*n + 29

und kann dies gemäß der oben verwendeten Argumentation zu:

2*3*5 * n + 1
2*3*5 * n + 7
2*3*5 * n + 11
2*3*5 * n + 13
2*3*5 * n + 17
2*3*5 * n + 19
2*3*5 * n + 23
2*3*5 * n + 29

vereinfachen, wiederum mit n = 1, 2, 3, ...

Hier fehlen dann noch einige Zahlen kleiner als 31, die noch wie folgt berücksichtigt werden können:

2*3*5 * n + 1
2*3*5 * n + 7
2*3*5 * n + 11
2*3*5 * n + 13
2*3*5 * n - 13
2*3*5 * n - 11
2*3*5 * n - 7
2*3*5 * n - 1

mit n = 1, 2, 3, ... und zuletzt noch

2*3*5 - 17
2*3*5 - 19
2*3*5 - 23
 

Bernhard

Registriertes Mitglied
Für kleine n kann man aus diesen Reihen dann einfache Formeln für die Berechnng der Anzahl der n-Primzahlen unterhalb einer frei wählbaren Schranke ableiten.

Für große n muss man jedoch alle Primzahlen bis \( \Pi_{i=1}^n p_n \) berücksichtigen und das werden sehr schnell sehr viele Primzahlen.
 

Bernhard

Registriertes Mitglied
Den extended Meissel-Lehmer-Algo in C++ (für MS-VisualStudio 2010) habe ich privat mal für einen PC programmiert, inklusive Speicherverwaltung. Für pi(1e15) ergibt sich eine Rechenzeit von etwa einer Stunde, was mit den Werten des Originalpapers vergleichbar ist. P2(1e16) habe ich auch mal berechnen lassen, um zu sehen, ob das Programm überhaupt durchläuft. Diese Berechnung benötigt einige Minuten.

Wer den Quelltext haben will, kann sich gern per PN melden. Es ist lohnend nachzuvollziehen, wie der Algo arbeitet.
 

Bernhard

Registriertes Mitglied
2*3*5 * n + 1
2*3*5 * n + 7
2*3*5 * n + 11
2*3*5 * n + 13
2*3*5 * n + 17
2*3*5 * n + 19
2*3*5 * n + 23
2*3*5 * n + 29

vereinfachen, wiederum mit n = 1, 2, 3, ...
Das kann man noch wie folgt "aufräumen". Es sollen alle "3-Primzahlen" (p_3 = 5) dargestellt werden:

z = 30n -1
z = 30n - p_n

Mit p_n < 30 und n > 3. Das sind genau die sieben Primzahlen, 7,11,13,17,19,23 und 29. Produkte aus diesen Primzahlen wären im Prinzip auch zulässig, sind aber alle größer als 30 und fallen deshalb weg.

Das negative Vorzeichen ist formal etwas geschickter als das + , damit man mit n=1 auch wirklich alle Zahlen bekommt, die weder durch 2, 3 und 5 teilbar sind.
 

Bernhard

Registriertes Mitglied
Den extended Meissel-Lehmer-Algo in C++ (für MS-VisualStudio 2010) habe ich privat mal für einen PC programmiert, inklusive Speicherverwaltung. Für pi(1e15) ergibt sich eine Rechenzeit von etwa einer Stunde, was mit den Werten des Originalpapers vergleichbar ist. P2(1e16) habe ich auch mal berechnen lassen, um zu sehen, ob das Programm überhaupt durchläuft. Diese Berechnung benötigt einige Minuten.
Mit den Verbesserungen von Deleglise und Rivat (1996) kann man mit y = sqrt(x) den Speicherbedarf der Berechnung deutlich reduzieren und damit auch die Rechenzeit. Für diese Wahl von y fällt dann auch die Berechnung von P2 weg. Die Rechenzeit für pi(1e15) reduziert sich damit auf übersichtliche 6 Minuten (etwa) und für pi(1e16) auf ca. 20 Minuten.
 
Oben