Primzählfunktion – Wikipedia
Funktion, die die Anzahl der Primzahlen darstellt, die kleiner oder gleich einer bestimmten Anzahl sind
In der Mathematik ist die Primzählfunktion ist die Funktion, die die Anzahl der Primzahlen zählt, die kleiner oder gleich einer reellen Zahl sind x.[1][2] Es wird mit bezeichnet π((x) (unabhängig von der Nummer π).
Geschichte[edit]
Von großem Interesse für die Zahlentheorie ist die Wachstumsrate der Primzählfunktion.[3][4] Es wurde Ende des 18. Jahrhunderts von Gauß und Legendre als ungefähr vermutet
in dem Sinne, dass
Diese Aussage ist der Primzahlsatz. Eine äquivalente Aussage ist
Dabei ist li die logarithmische Integralfunktion. Der Primzahlsatz wurde erstmals 1896 von Jacques Hadamard und Charles de la Vallée Poussin unabhängig voneinander unter Verwendung der Eigenschaften der 1859 von Riemann eingeführten Riemannschen Zetafunktion bewiesen. Es wurden Beweise für den Primzahlsatz gefunden, bei denen die Zetafunktion oder die komplexe Analyse nicht verwendet wurden um 1948 von Atle Selberg und von Paul Erdős (größtenteils unabhängig).[5]
De la Vallée Poussin hat dies 1899 bewiesen (siehe auch Satz 23 von[6])
für eine positive Konstante ein. Hier, Ö(…) ist der große Ö Notation.
Genauere Schätzungen von
sind jetzt bekannt. Zum Beispiel hat Kevin Ford das im Jahr 2002 bewiesen[7]
- .
Im Jahr 2016 erwies sich Tim Trudgian als explizite Obergrenze für den Unterschied zwischen
und
::
zum
.[8]
Für die meisten Werte von
wir sind interessiert an (dh wann
ist nicht unangemessen groß)
ist größer als
. Jedoch,
ist dafür bekannt, das Vorzeichen unendlich oft zu ändern. Eine Diskussion hierzu finden Sie unter Skewes ‘Nummer.
Genaue Form[edit]
Von großer Bedeutung ist, dass Bernhard Riemann bewiesen hat, dass die Primzählfunktion genau ist[9]
wo
- ,
μ((n) ist die Möbius-Funktion, li (x) ist die logarithmische Integralfunktion, ρ indiziert jede Null der Riemannschen Zetafunktion und li (xρ / n) wird nicht mit einem Astschnitt ausgewertet, sondern als Ei (ρ/.n ln x) wo Ei (x) ist das Exponentialintegral. Entsprechend, wenn die trivialen Nullen gesammelt und die Summe genommen wird nur über die nicht trivialen Nullen ρ der Riemannschen Zeta-Funktion also π((x) kann geschrieben werden
- .
Die Riemann-Hypothese legt nahe, dass jede solche nicht triviale Null liegt Re(s) = 1/.2.
Tabelle π((x), x / ln xund li (x)[edit]
Die Tabelle zeigt, wie die drei Funktionen funktionieren π((x), x / ln x und li (x) Vergleiche bei Potenzen von 10. Siehe auch,[3][10][11] und[12]
-
x π((x) π((x) – x / ln x li (x) – π((x) x /. π((x) x / ln x% Fehler 10 4 −0.3 2.2 2.500 -7,5% 102 25 3.3 5.1 4.000 13,20% 103 168 23 10 5,952 13,69% 104 1,229 143 17 8.137 11,64% 105 9,592 906 38 10.425 9,45% 106 78.498 6,116 130 12.740 7,79% 107 664,579 44,158 339 15.047 6,64% 108 5,761,455 332,774 754 17.357 5,78% 109 50,847,534 2,592,592 1.701 19.667 5,10% 1010 455,052,511 20.758.029 3,104 21.975 4,56% 1011 4,118,054,813 169.923.159 11.588 24.283 4,13% 1012 37,607,912,018 1.416.705.193 38,263 26.590 3,77% 1013 346,065,536,839 11.992.858.452 108.971 28.896 3,47% 1014 3,204,941,750,802 102,838,308,636 314.890 31.202 3,21% 1015 29.844.570.422.669 891,604,962,452 1,052,619 33.507 2,99% 1016 279,238,341,033,925 7,804,289,844,393 3,214,632 35.812 2,79% 1017 2,623,557,157,654,233 68.883.734.693.281 7,956,589 38.116 2,63% 1018 24.739.954.287.740.860 612.483.070.893.536 21.949.555 40.420 2,48% 1019 234,057,667,276,344,607 5,481,624,169,369,960 99.877.775 42,725 2,34% 1020 2,220,819,602,560,918,840 49.347.193.044.659.701 222,744,644 45.028 2,22% 1021 21.127.269.486.018.731.928 446.579.871.578.168.707 597,394,254 47.332 2,11% 1022 201.467.286.689.315.906.290 4,060,704,006,019,620,994 1,932,355,208 49.636 2,02% 1023 1,925,320,391,606,803,968,923 37.083.513.766.578.631.309 7,250,186,216 51.939 1,93% 1024 18.435.599.767.349.200.867.866 339.996.354.713.708.049.069 17.146.907.278 54.243 1,84% 1025 176.846.309.399.143.769.411.680 3,128,516,637,843,038,351,228 55.160.980.939 56,546 1,77% 1026 1,699,246,750,872,437,141,327,603 28.883.358.936.853.188.823.261 155,891,678,121 58.850 1,70% 1027 16.352.460.426.841.640.446.427.399 267,479,615,610,131,274,163,365 508,666,658,006 61.153 1,64%
In der Online-Enzyklopädie der ganzzahligen Sequenzen wird die π((x) Spalte ist Sequenz OEIS: A006880, π((x) – x/ ln x ist Sequenz OEIS: A057835, und li (x) – π((x) ist Sequenz OEIS: A057752.
Der Wert für π(1024) wurde ursprünglich von J. Buethe, J. Franke, A. Jost und T. Kleinjung unter Annahme der Riemann-Hypothese berechnet.[13]
Es wurde später in einer Berechnung von DJ Platt bedingungslos verifiziert.[14]
Der Wert für π(1025) geht auf J. Buethe, J. Franke, A. Jost und T. Kleinjung zurück.[15]
Der Wert für π(1026) wurde von DB Staple berechnet.[16] Alle anderen vorherigen Einträge in dieser Tabelle wurden im Rahmen dieser Arbeit ebenfalls überprüft.
Der Wert für 1027 wurde 2015 von David Baugh und Kim Walisch veröffentlicht.[17]
Algorithmen zur Bewertung π((x)[edit]
Ein einfacher Weg zu finden
, wenn
ist nicht zu groß, ist das Sieb von Eratosthenes zu verwenden, um die Primzahlen kleiner oder gleich zu produzieren
und dann, um sie zu zählen.
Eine aufwändigere Art zu finden
ist auf Legendre zurückzuführen (unter Verwendung des Einschluss-Ausschluss-Prinzips): gegeben
, wenn
sind verschiedene Primzahlen, dann ist die Anzahl der ganzen Zahlen kleiner oder gleich
die durch Nr. teilbar sind
ist
(wo
bezeichnet die Bodenfunktion). Diese Zahl ist daher gleich
wenn die Zahlen
sind die Primzahlen kleiner oder gleich der Quadratwurzel von
.
Der Meissel-Lehmer-Algorithmus[edit]
In einer Reihe von Artikeln, die zwischen 1870 und 1885 veröffentlicht wurden, beschrieb (und verwendete) Ernst Meissel eine praktische kombinatorische Art der Bewertung
. Lassen
,
sei der Erste
Primzahlen und bezeichnen mit
die Anzahl der natürlichen Zahlen nicht größer als
die durch Nr. teilbar sind
. Dann
Gegeben eine natürliche Zahl
, wenn
und wenn
, dann
Mit diesem Ansatz berechnete Meissel
, zum
gleich 5×105106107und 108.
1959 erweiterte und vereinfachte Derrick Henry Lehmer Meissels Methode. Definieren Sie wirklich
und für natürliche Zahlen
und
,
als die Anzahl der Zahlen nicht größer als m mit genau k Primfaktoren, alle größer als
. Weiterhin einstellen
. Dann
wobei die Summe tatsächlich nur endlich viele Nicht-Null-Terme hat. Lassen
bezeichnen eine ganze Zahl so, dass
und setzen
. Dann
und
wann
≥ 3. Daher
Die Berechnung von
kann auf diese Weise erhalten werden:
- ,
wo die Summe über Primzahlen liegt.
Auf der anderen Seite die Berechnung von
kann nach folgenden Regeln durchgeführt werden:
Mit seiner Methode und einem IBM 701 konnte Lehmer rechnen
.
Weitere Verbesserungen dieser Methode wurden von Lagarias, Miller, Odlyzko, Deléglise und Rivat vorgenommen.[18]
Andere Primzählfunktionen[edit]
Andere Primzählfunktionen werden ebenfalls verwendet, da sie bequemer zu handhaben sind. Eine davon ist Riemanns Primzählfunktion, die üblicherweise als bezeichnet wird
oder
. Dies hat Sprünge von 1 /n für Hauptmächte pn, wobei es bei Diskontinuitäten einen Wert auf halbem Weg zwischen den beiden Seiten annimmt. Dieses hinzugefügte Detail wird verwendet, da dann die Funktion durch eine inverse Mellin-Transformation definiert werden kann. Formal können wir definieren
durch
wo p ist eine Primzahl.
Wir können auch schreiben
wo
ist die von Mangoldt-Funktion und
Die Möbius-Inversionsformel ergibt dann
Kenntnis der Beziehung zwischen log der Riemannschen Zeta-Funktion und der von Mangoldt-Funktion
und unter Verwendung der Perron-Formel, die wir haben
Die Chebyshev-Funktion gewichtet Primzahlen oder Primzahlen pn von ln (p):
Formeln für Primzählfunktionen[edit]
Es gibt zwei Arten von Formeln für Primzählfunktionen: arithmetische Formeln und analytische Formeln. Analytische Formeln für die Primzählung waren die ersten, die zum Beweis des Primzahlsatzes verwendet wurden. Sie stammen aus der Arbeit von Riemann und von Mangoldt und sind allgemein als explizite Formeln bekannt.[19]
Wir haben den folgenden Ausdruck für ψ::
wo
Hier sind ρ die Nullen der Riemannschen Zeta-Funktion im kritischen Streifen, wobei der Realteil von ρ zwischen Null und Eins liegt. Die Formel gilt für Werte von x größer als eins, welches die Region von Interesse ist. Die Summe über den Wurzeln ist bedingt konvergent und sollte in der Reihenfolge des zunehmenden Absolutwerts des Imaginärteils genommen werden. Beachten Sie, dass dieselbe Summe über den trivialen Wurzeln den letzten Subtrahend in der Formel ergibt.
Zum
Wir haben eine kompliziertere Formel
Auch hier gilt die Formel für x > 1, während ρ sind die nichttrivialen Nullen der Zeta-Funktion, die nach ihrem absoluten Wert geordnet sind, und wiederum ist das letztere Integral mit Minuszeichen genau die gleiche Summe, jedoch über den trivialen Nullen. Der erste Begriff li (x) ist die übliche logarithmische Integralfunktion; der Ausdruck li (xρ) im zweiten Term sollte als Ei (ρ ln x), wobei Ei die analytische Fortsetzung der Exponentialintegralfunktion von negativen Reals zur komplexen Ebene ist, wobei der Zweig entlang der positiven Realen geschnitten ist.
Die Möbius-Inversionsformel gibt uns also[20]
Gültig für x > 1, wo
ist Riemanns R-Funktion[21] und μ((n) ist die Möbius-Funktion. Die letztere Serie dafür ist als Gram-Serie bekannt.[22][23] weil
für alle
.
Die Summe über nicht triviale Zeta-Nullen in der Formel für
beschreibt die Schwankungen von
während die übrigen Begriffe die geben “glatt” Teil der Primzählfunktion,[24] so kann man verwenden
als bester Schätzer von
zum x > 1.
Die Amplitude der “laut” Teil ist heuristisch über
so können die Schwankungen der Verteilung der Primzahlen mit der Δ-Funktion klar dargestellt werden:
Eine umfangreiche Tabelle der Werte von Δ (x) ist verfügbar.[11]
Ungleichungen[edit]
Hier sind einige nützliche Ungleichungen für π((x).
zum x ≥ 17.
Die linke Ungleichung gilt für x ≥ 17 und die rechte Ungleichung gilt für x> 1. Die Konstante 1.25506 ist
bis 5 Dezimalstellen, as
hat seinen Maximalwert bei x = 113.[25]
Pierre Dusart hat 2010 bewiesen:
- zum , und
- zum .[26]
Hier sind einige Ungleichungen für die nth prime, pn. Die Obergrenze stammt von Rosser (1941),[27] der untere zu Dusart (1999):[28]
zum n ≥ 6.
Die linke Ungleichung gilt für n ≥ 2 und die rechte Ungleichung gilt für n ≥ 6.
Eine Annäherung für die nDie Primzahl ist
Ramanujan[29] bewiesen, dass die Ungleichung
gilt für alle ausreichend großen Werte von
.
Im,[26] Dusart bewies (Satz 6.6), dass z
,
- ,
und (Satz 6.7), dass z
,
- .
In jüngerer Zeit Dusart[30]
hat bewiesen (Satz 5.1), dass z
,
und das, z
,
- Die Riemannsche Hypothese[edit]
Die Riemann-Hypothese entspricht einer viel engeren Grenze für den Fehler in der Schätzung für
und damit zu einer regelmäßigeren Verteilung der Primzahlen,
Speziell,[31]
Siehe auch[edit]
Verweise[edit]
- ^ Bach, Eric; Shallit, Jeffrey (1996). Algorithmische Zahlentheorie. MIT Press. Band 1 Seite 234 Abschnitt 8.8. ISBN 0-262-02405-5.
- ^ Weisstein, Eric W. “Primzählfunktion”. MathWorld.
- ^ ein b “Wie viele Primzahlen gibt es?”. Chris K. Caldwell. Abgerufen 2008-12-02.
- ^ Dickson, Leonard Eugene (2005). Geschichte der Zahlentheorie, Bd. I: Teilbarkeit und Ursprünglichkeit. Dover-Veröffentlichungen. ISBN 0-486-44232-2.
- ^ Irland, Kenneth; Rosen, Michael (1998). Eine klassische Einführung in die moderne Zahlentheorie (Zweite Ausgabe). Springer. ISBN 0-387-97329-X.
- ^ AE Ingham (2000). Die Verteilung von Primzahlen. Cambridge University Press. ISBN 0-521-39789-8.
- ^ Kevin Ford (November 2002). “Vinogradovs Integral und Grenzen für die Riemannsche Zeta-Funktion” (PDF). Proc. London Math. Soc. 85 (3): 565–633. arXiv:1910.08209. doi:10.1112 / S0024611502013655. S2CID 121144007.
- ^ Tim Trudgian (Februar 2016). “Aktualisieren des Fehlerterms im Primzahlsatz”. Ramanujan Journal. 39 (2): 225–234. arXiv:1401.2689. doi:10.1007 / s11139-014-9656-6. S2CID 11013503.
- ^ “Die Schwankungen der Primzählfunktion pi (x)”. www.primefan.ru. Abgerufen 17. Mai 2019.
- ^ “Wertetabellen von pi (x) und von pi2 (x)”. Tomás Oliveira e Silva. Abgerufen 2008-09-14.
- ^ ein b “Werte von π((x) und Δ (x) für verschiedene Werte von x“. Andrey V. Kulsha. Abgerufen 2008-09-14.
- ^ “Eine Wertetabelle von pi (x)”. Xavier Gourdon, Pascal Sebah, Patrick Demichel. Abgerufen 2008-09-14.
- ^ “Bedingte Berechnung von pi (1024)”. Chris K. Caldwell. Abgerufen 03.08.2010.
- ^ Platt, David J. (2012). “Computing π((x) Analytisch)”. arXiv:1203,5712 [math.NT].
- ^ “Wie viele Primzahlen gibt es?”. J. Buethe. Abgerufen 2015-09-01.
- ^ Staple, Douglas (19. August 2015). Der kombinatorische Algorithmus zur Berechnung von pi (x) (These). Dalhousie Universität. Abgerufen 2015-09-01.
- ^ Walisch, Kim (6. September 2015). “Neuer bestätigter pi (10 ^ 27) Primzählungsfunktionsdatensatz”. Mersenne Forum.
- ^ Marc Deleglise; Joel Rivat (Januar 1996). “Computing π((x): Die Methode von Meissel, Lehmer, Lagarias, Miller, Odlyzko” (PDF). Mathematik der Berechnung. 65 (213): 235–245. doi:10.1090 / S0025-5718-96-00674-6.
- ^ Titchmarsh, EC (1960). Die Theorie der Funktionen, 2. Aufl. Oxford University Press.
- ^ Riesel, Hans; Göhl, Gunnar (1970). “Einige Berechnungen bezogen sich auf Riemanns Primzahlformel”. Mathematik der Berechnung. Amerikanische Mathematische Gesellschaft. 24 (112): 969–983. doi:10.2307 / 2004630. ISSN 0025-5718. JSTOR 2004630. HERR 0277489.
- ^ Weisstein, Eric W. “Riemann-Zählfunktion”. MathWorld.
- ^ Riesel, Hans (1994). Primzahlen und Computermethoden zur Faktorisierung. Fortschritte in der Mathematik. 126 (2. Aufl.). Birkhäuser. S. 50–51. ISBN 0-8176-3743-5.
- ^ Weisstein, Eric W. “Gramm-Serie”. MathWorld.
- ^ “Die Codierung der Primverteilung durch die Zeta-Nullen”. Matthew Watkins. Abgerufen 2008-09-14.
- ^ Rosser, J. Barkley; Schönfeld, Lowell (1962). “Ungefähre Formeln für einige Funktionen von Primzahlen”. Illinois J. Math. 6: 64–94. doi:10.1215 / ijm / 1255631807. ISSN 0019-2082. Zbl 0122.05001.
- ^ ein b Dusart, Pierre (2. Februar 2010). “Schätzungen einiger Funktionen über Primzahlen ohne relative Luftfeuchtigkeit”. arXiv:1002.0442v1 [math.NT].
- ^ Rosser, Barkley (1941). “Explizite Grenzen für einige Funktionen von Primzahlen”. American Journal of Mathematics. 63 (1): 211–232. doi:10.2307 / 2371291. JSTOR 2371291.
- ^ Dusart, Pierre (1999). “Die k-te Primzahl ist größer als k (lnk + lnlnk-1) für k> = 2”. Mathematik der Berechnung. 68 (225): 411–415. doi:10.1090 / S0025-5718-99-01037-6.
- ^ Berndt, Bruce C. (06.12.2012). Ramanujans Notizbücher, Teil IV. Springer Science & Business Media. S. 112–113. ISBN 9781461269328.
- ^ Dusart, Pierre (Januar 2018). “Explizite Schätzungen einiger Funktionen über Primzahlen”. Ramanujan Journal. 45 (1): 225–234. doi:10.1007 / s11139-016-9839-4. S2CID 125120533.
- ^ Schönfeld, Lowell (1976). “Schärfere Grenzen für die Chebyshev-Funktionen θ((x) und ψ((x). II”. Mathematik der Berechnung. Amerikanische Mathematische Gesellschaft. 30 (134): 337–360. doi:10.2307 / 2005976. ISSN 0025-5718. JSTOR 2005976. HERR 0457374.
Externe Links[edit]
Recent Comments