Sieb des Eratosthenes

[Bernhard]

Hallo Major T.O.M.,

Ich hab dann aber festgestellt, dass es nach der 3 dann nicht mehr viel bringt.

ja, das ist richtig. Der Algorithmus wird dadurch schnell wieder unübersichtlich.

 

[Major T.O.M.]

Kommt darauf an wie man es implementiert. Ich schreibe ja nicht die einzelnen Formeln in den Code. Unübersichlich ist es bei mir nicht. Aber die Rechenzeit ist halt schlecht. Ich habe es in Matlab programmiert. In der Matlab-Funktion primes wird ein Vektor mit allen ungeraden Zahlen von 1 bis n erstellt und anschließend alle durch 3 teilbaren auf 0 Null gesetzt. Dann die durch 5, 7, 11, 13, 17 ... teilbaren (bis sqrt). Das praktische ist, dass zum Beispiel jede siebte Zahl in dem Vektor durch 7 teilbar ist. Bei meinem Vektor ist das nicht der Fall. Das heißt es müsste jede Zahl auf Teilbarkeit geprüft werden. Das macht den Algorithmus sehr langsam. Von daher habe ich das ganze verworfen.

b) Mit dem Meissel-Lehmer-Algorithmus kann man mit diesem Sieb dann zB den maximalen Wert von pi(1e13) berechnen, wobei dann die Rechenzeit schon mehrere Minuten betragen kann. Bei meiner Implementierung liege ich aktuell für diesen Wert bei ca. 20 Minuten Rechenzeit. Der korrekte Wert für pi(1e13) kann mit den Werten dieser Seite https://de.wikipedia.org/wiki/Primzahlsatz#Zahlenbeispiele kontrolliert werden.

Interessanter Link. Da sieht man, dass die Approximation x/ln(x) eigentlich relativ schlecht ist mit mehr als 1% Abweichung. Diese Li-Funktion ist ja deutlich genauer. Da stimmen bei 10^28 und 10^29 die ersten 14 Stellen überein.

 

[Bernhard]

Da sieht man, dass die Approximation x/ln(x) eigentlich relativ schlecht ist mit mehr als 1% Abweichung.

Bei der gröbsten Approximation (und auch den besseren Näherungen) steht für mich vor allem die Frage im Raum, warum da ausgerechnet der Logarithmus so einen wichtige Rolle spielt. Dafür gibt es sicher eine schlaue Erklärung.

Diese Li-Funktion ist ja deutlich genauer. Da stimmen bei 10^28 und 10^29 die ersten 14 Stellen überein.

Noch faszinierender finde ich die Riemann-Funktion. Die ist auf die Primzahlfunktion vom Verlauf her wirklich maßgeschneidert.

 

[Bernhard]

Kommt darauf an wie man es implementiert.

Man kann sich da unterschiedliche Ziele setzen.

a) Möglichst schnell Primzahlen berechnen
b) Möglichst viele Primzahlen
c) Möglichst schnell, möglichst viele usw.

Interessant ist dabei eine Implementierung, die echte Bits nutzt. So kann man Speicher sparen und damit möglichst viele Primzahlen berechnen, muss sich dafür aber auch mit Bit-Operatoren bei der Programmierung beschäftigen.

 

[Major T.O.M.]

Noch faszinierender finde ich die Riemann-Funktion. Die ist auf die Primzahlfunktion vom Verlauf her wirklich maßgeschneidert.

Aber kann man das auch effizient berechnen? Ich meine x/ln(x) bzw. x/(ln(x)-1) kann man relativ leicht berechnen. Die Li-Funktion kann man immerhin noch mit Quadraturformeln gut approximieren.

 

[Bernhard]

Aber kann man das auch effizient berechnen?

Laut Wolfram benutzt man dazu besser die Gram-Reihe: https://mathworld.wolfram.com/GramSeries.html muss dabei dann aber die riemannsche Zetafunktion berechnen. Mit der Funktion zeta habe ich mich bisher noch wenig beschäftigt.

 

[Major T.O.M.]

Bei der gröbsten Approximation (und auch den besseren Näherungen) steht für mich vor allem die Frage im Raum, warum da ausgerechnet der Logarithmus so einen wichtige Rolle spielt. Dafür gibt es sicher eine schlaue Erklärung.

Ich habe mir mal ein bisschen Gedanken über diese Fragestellung gemacht. Ich hatte zwar mal eine Zahlentheorievorlesung gehört, aber der Beweis verwendet ja haufenweise andere Sätze und Lemmata, sodass man eigentlich gar nicht mehr durchblickt, was da eigentlich gerade bewiesen wird. Das Folgende ist kein mathematischer Beweis, sondern ist nur dazu da, um grob zu veranschaulichen, was der LN mit der Verteilung der Primzahlen zu tun hat. Wie wir ja bereits festgestellt haben, wird beim Sieb des Eratosthenes zunächst jede zweite Zahl gestrichen, dann jede dritte, fünfte, siebte, eltfte, ... Wenn wir also bei einem Wert x angekommen sein werden und alle Vielfachen von Primzahlen <= x durchgestrichen haben, kann der Anteil der noch nicht durchgestrichenen Zahlen >x duch folgende Funktion beschrieben werden:
\begin{align}
\rho\left(x\right) := \prod_{p\leq x,\text{ prim}} \frac{p-1}p
\end{align}
In Bereichen weit größer x werden noch einige Zahlen durchgestrichen werden. Im Bereich wenig größer als x kann die Funktion als ungefähre Primzahldichte aufgefasst werden. Falls x eine Primzahl ist, sind alle Zahlen zwischen x und x^2, die noch nicht durchgestrichen sind, Primzahlen. Somit ist der Anteil der Primzahlen in diesem Bereich in etwa rho(x).

Die Funktion rho(x) ist eine monoton fallende Stufenfunktion und hat genau bei bei allen Primzahlen einen Sprung und zwar gilt für eine Primzahl x
\begin{align}
\rho\left(x\right) = \frac{x-1}x \rho\left(x-1\right)
\end{align}
Umgeformt:
\begin{align}
\rho\left(x\right)-\rho\left(x-1\right) = -\frac 1x \rho\left(x-1\right)
\end{align}
Die Wahrscheinlichkeit, dass eine ganze Zahl x eine Primzahl ist, ist in etwa rho(x-1). Die linke Seite kann als Diffenzenquotient aufgefasst werden. Der Differenzenquotient ist jedoch 0, wenn sich im Intervall (x-1, x] keine Primzahl befindet. Zur Approximation durch eine stetig-differenzierbare Funktion stelle ich die folgende DGL auf:
\begin{align}
\dot{\tilde\rho}\left(x\right) = -\frac 1x \tilde\rho\left(x\right)^2
\end{align}
Als Lösung ergibt sich
\begin{align}
\tilde\rho\left(x\right) = \frac 1{\ln\left(x\right)-c}
\end{align}
wobei die Konstante c durch die Anfangswerte zu berechnen ist.

Damit wird auch klar, warum die die Li-Funktion soviel besser ist als x/ln(x). Bei der Li Funktion wird die Dichte integriert. Bei x/ln(x) entsteht ein großer Fehler, die im Bereich der kleinen Zahlen eine viel höhere Primzahldichte herrscht, was bei x/ln(x) nicht berücksichtigt wird.

 

[Bernhard]

kann der Anteil der noch nicht durchgestrichenen Zahlen >x duch folgende Funktion beschrieben werden:

Ziemlich interessanter Ansatz, allerdings noch nicht ganz ohne Rückfragen:

Wenn ich mir die Zahlen 1 bis 100 mal hinschreibe und die Vielfachen der Primzahlen streiche bleiben mir nach der 2 zuerst 50 Zahlen übrig, nach der 3 noch 33 und nach der 5 noch 26.

Jeweils geteilt durch 100 ergeben sich die Anteile zu: 1/2, 1/3, 13/50, usw.

Das ist eine etwas andere Reihe, als von Dir angegeben.

Bei dir ergibt sich: 1/2, 1/3, 4/15, usw.

Woran liegts? Wie kommst du auf die erste Formel mit dem Produktzeichen?

Abgesehen von diesem Detail, kommst du schon auf recht interessante Ergebnisse ....

EDIT: Eventuell kommt man mit einer kleinen Korrektur noch weiter. Die berechneten Zahlen entsprechen doch der Funktion Phi im Meissel-Lehmer-Algorithmus (?) und wird gerne rekursiv berechnet, was dann weitgehend deiner Produktformel entspricht. Wurde da nur die Eins übersehen?

 

[Bernhard]

kann der Anteil der noch nicht durchgestrichenen Zahlen >x duch folgende Funktion beschrieben werden:
\begin{align}
\rho\left(x\right) := \prod_{p\leq x,\text{ prim}} \frac{p-1}p
\end{align}

Man müsste mal prüfen, ob nicht
\begin{align}
\rho\left(x\right) = N^{-1}\lfloor N\prod_{i=1}^a \frac{p_i-1}{p_i} \rfloor
\end{align}
mit $$x = p_a$$ gilt. Dann würde nämlich auch
\begin{align}
\Phi (N, a) = \lfloor N\prod_{i=1}^a \frac{p_i-1}{p_i} \rfloor
\end{align}
gelten, und damit ließe sich dann der Meissel-Lehmer-Algorithmus nochmal enorm beschleunigen. Die meiste Rechenzeit wird bei diesem Algorithmus nämlich auf diese Funktion verwendet.

EDIT: Die halben eckigen Klammer bezeichnen die Abrundungsfunktion

 

[Major T.O.M.]

Ziemlich interessanter Ansatz, allerdings noch nicht ganz ohne Rückfragen:

Wenn ich mir die Zahlen 1 bis 100 mal hinschreibe und die Vielfachen der Primzahlen streiche bleiben mir nach der 2 zuerst 50 Zahlen übrig, nach der 3 noch 33 und nach der 5 noch 26.

Jeweils geteilt durch 100 ergeben sich die Anteile zu: 1/2, 1/3, 13/50, usw.

Das ist eine etwas andere Reihe, als von Dir angegeben.

Bei dir ergibt sich: 1/2, 1/3, 4/15, usw.

Woran liegts? Wie kommst du auf die erste Formel mit dem Produktzeichen?

Abgesehen von diesem Detail, kommst du schon auf recht interessante Ergebnisse ....

EDIT: Eventuell kommt man mit einer kleinen Korrektur noch weiter. Die berechneten Zahlen entsprechen doch der Funktion Phi im Meissel-Lehmer-Algorithmus (?) und wird gerne rekursiv berechnet, was dann weitgehend deiner Produktformel entspricht. Wurde da nur die Eins übersehen?

Naja, 4/15=0,26667, also ist es für 100 doch nah dran.

Du hattest ja in deinem Startbeitrag die Formeln

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

Das sind also 8 von 30, gekürz 4/15. Wenn du also anstatt 100 ein vielfaches von 30 (bzw. 15) nimmst, dann sollte es aufgehen. Aber auch für andere Zählen müsste es im Unendlichen immer Näher an 4/15 kommen.

Die Idee hinter der Formel ist ganz einfach. Mit jeder Primzahl p streiche ich 1/p der übrigen Zahlen. Übrig bleiben also (p-1)/p.

 

[Bernhard]

Die Idee hinter der Formel ist ganz einfach. Mit jeder Primzahl p streiche ich 1/p der übrigen Zahlen. Übrig bleiben also (p-1)/p.

Ok. Man findet die Formel auch in der Arbeit von Lehmer aus dem Jahr 1958. Es ist eine gute Näherungsformel.

 

[Bernhard]

Zur Approximation durch eine stetig-differenzierbare Funktion stelle ich die folgende DGL auf:
\begin{align}
\dot{\tilde\rho}\left(x\right) = -\frac 1x \tilde\rho\left(x\right)^2
\end{align}

Gibt es für das Quadrat auf der rechten Seite eine anschauliche Begründung? Falls nein, hat man immer noch die Erfolge der Funktion li(x).

Im Rahmen der vorgestellten Herleitung ist das Quadrat nicht offensichtlich.

 

[Major T.O.M.]

Das Quadrat kommt hinzu, weil die Wahrscheinlichkeit, dass eine ganze Zahl eine Primzahl ist mit rho(x-1) geschätzt werden kann.

 

[Bernhard]

Das Quadrat kommt hinzu, weil die Wahrscheinlichkeit, dass eine ganze Zahl eine Primzahl ist mit rho(x-1) geschätzt werden kann.

Ok. Der Differenzenquotient ist nur ungleich Null, wenn x eine Primzahl ist. Um die Steigung der Funktion abzuschätzen, muss rechts deshalb einmal mit rho multipliziert werden.

 

[Major T.O.M.]

Ja genau. Wie gesagt. Das soll kein mathematisch sauberer Beweis sein, sondern nur zur Veranschaulichung. Vielleicht kann man das auch noch irgendwie diskret veranschaulichen. Ich bin eben mehr im angewandten Bereich unterwegs. Deshalb die Idee mit der DGL.

 

[Bernhard]

Deshalb die Idee mit der DGL.

Ich finde deine anschauliche Herleitung der Funktion li(x) richtig gut. Großes Lob meinerseits.

Ausgangspunkt ist ja das https://de.wikipedia.org/wiki/Euler-Produkt mit s=1. Der Grenzwert strebt also nach \(1/\zeta(1)\), was damit dann, wie bereits bekannt, gegen Null strebt.

Man kann mit l'Hospital noch zeigen, dass x/ln(x) und li(x) das gleiche Grenzwertverhalten haben.

Will man tiefer in die Thematik einsteigen, lohnt sich der englischsprachige Artikel zur Primzahlfunktion: https://en.wikipedia.org/wiki/Prime-counting_function#Exact_form , Abschnitt Exakte Form als Erklärung für diese Grafik: https://en.wikipedia.org/wiki/Prime-counting_function#/media/File:Riemann_Explicit_Formula.gif im gleichen Artikel.

Was auch eine Motivation ergibt, sich mal die nicht-trivialen Nullstellen der zeta-Funktion anzusehen. Siehe auch Referenz 10 dieses Artikels.

 

[Bernhard]

Ich bin eben mehr im angewandten Bereich unterwegs.

Off topic: Ich schaue zur Zeit in dieser Hinsicht auch recht gern den Kanal Numberphile auf YouTube. Etwas langatmig, aber ganz toll der Clip zum Satz von Ptolemaios:
A Miraculous Proof (Ptolemy's Theorem) - Numberphile (nur englisch, Numberphile 09.02.2020)

EDIT: Zvezdelina Stankova zeigt in diesem Clip sehr schön, (glaube ich) auch eine Anwendung der riemannschen Zahlenkugel.

 

[Bernhard]

Was auch eine Motivation ergibt, sich mal die nicht-trivialen Nullstellen der zeta-Funktion anzusehen.

zB:
Berechnungsverfahren zur riemannschen Zeta-Funktion (Wikipedia)
Probabilistic models for Gram's Law (Hanga, Hughes, arxiv.org, 08.11.2019)

 

[Major T.O.M.]

Off topic: Ich schaue zur Zeit in dieser Hinsicht auch recht gern den Kanal Numberphile auf YouTube. Etwas langatmig, aber ganz toll der Clip zum Satz von Ptolemaios:
A Miraculous Proof (Ptolemy's Theorem) - Numberphile (nur englisch, Numberphile 09.02.2020)

EDIT: Zvezdelina Stankova zeigt in diesem Clip sehr schön, (glaube ich) auch eine Anwendung der riemannschen Zahlenkugel.

Auch sehr interessant. Ich meinte aber eigentlich, dass ich mit numerischer Mathematik zu tun habe. Genau genommen mit Differentialgleichungen und differential-algebraischen Gleichungen. Ich finde aber auch Zahlentheorie und sowas spannend.

 

[Bernhard]

Ich meinte aber eigentlich, dass ich mit numerischer Mathematik zu tun habe.

Beruflich - Als Student - Doktorand?

Genau genommen mit Differentialgleichungen und differential-algebraischen Gleichungen.

Ich habe in diesem Umfeld erst kürzlich gesehen, dass man sich da per numerischer Integration viel Arbeit sparen kann. Die Poissongleichung kann man zB entweder mit orthogonalen Funktionensystemen oder mit numerischer Integration lösen, wobei der zweite Ansatz deutlich schneller zu Ergebnissen führt.