In der Mathematik hat sich die Suche nach exakten Formeln mit allen Primzahlen, bestimmten Familien von Primzahlen oder der n- ten Primzahl im Allgemeinen als vergeblich erwiesen, was dazu geführt hat, dass mit ungefähren Formeln zufrieden ist. Diese Seite listet die wichtigsten Ergebnisse auf.
Die Hoffnung, eine genaue und einfache Formel zu erhalten, die die n-te Primzahl p n oder die Zahl π ( n ) von Primzahlen kleiner oder gleich n ergibt , stieß sehr früh auf die extreme Unregelmäßigkeit ihrer Verteilung , die zu Inhalten geführt hat mit weniger ehrgeizigen Zielen. Aber selbst die Suche nach Formeln, die nur Primzahlen enthalten, erweist sich als ziemlich enttäuschend. so ist es leicht zu zeigen , dass es keine Polynomfunktion nicht konstant P ( n ) , die nur die ersten Werte für alle ganzen Zahlen nehmen würde n oder sogar fast alle der n ; Tatsächlich wissen wir nicht einmal, ob es ein Polynom vom Grad> 1 gibt, das unendlich viele Primwerte annimmt.
Dies erklärt das Interesse von Eulers Bemerkung : Das quadratische Polynom P ( n ) = n 2 + n + 41 ist eine Primzahl für alle positiven ganzen Zahlen, die streng kleiner als 40 sind (beachten Sie, dass und wenn n ein Vielfaches von 41 ist, wird auch P ( n ) ein Vielfaches von 41 sein und daher keine Primzahl). Darüber hinaus ist 41 die größte „ Glücks-Euler-Zahl “, dh die größte ganze Zahl A, für die das Polynom n 2 + n + A für alle n streng kleiner als A - 1 ist . Dies folgt aus dem Stark-Heegner-Theorem , einem Ergebnis der Klassenfeldtheorie, das erst 1967 demonstriert wurde. In ähnlicher Weise erzeugen andere (höhergradige) Polynomformeln Sequenzen von Primzahlen. So ermöglichte es einer von ihnen 2010, einen neuen Rekord aufzustellen: eine Folge von 58 Primzahlen:
ist eine Primzahl für jede ganze Zahl n von –42 bis 15.Andere Formeln, die allgemeinere Funktionen verwenden, wie die von Mersenne , wurden in Betracht gezogen, wobei die bekannteste die von Fermat vermutete ist : F n = 2 2 n + 1 ist Primzahl für alle n . Wenn diese Zahlen (im Folgenden Fermat-Zahlen genannt ) tatsächlich Primzahlen für 0 ≤ n ≤ 4 sind , entdeckte Euler leider, dass die sechste, F 5 , durch 641 teilbar ist, was die Vermutung ruiniert; Derzeit denken wir im Gegenteil, dass F n immer zusammengesetzt ist, sobald n > 4 ist . In gleicher Weise erzeugt die Mills-Formel nur Primzahlen, hat jedoch den Nachteil, dass sie nur theoretisch ist.
Näherungsformeln für p n oder π ( n ) wurden erdacht XVIII th Jahrhundert, mit der Vermutung von kulminiert Legendre und Gauss . Wenn ihre einfachste Hypothese ein Jahrhundert später von Hadamard und La Vallée Poussin demonstriert wurde (es ist der Primzahlsatz ), wird die Schwierigkeit des Problems durch die Tatsache deutlich, dass eine von Gauß 'Vermutungen genauer ist und π ( n ) begrenzt. by , was angesichts der Tabellen dieser beiden Funktionen sehr plausibel erschien , hat sich jedoch als falsch herausgestellt, jedoch nur für gigantische Werte von n .
Genauere Ergebnisse und insbesondere eine gute Schätzung des Fehlerterms h ( n ) in der Formel p n = n ln n + h ( n ) sind noch zu vermuten (häufig abhängig von der Annahme von Riemann ); Unter den besten Ergebnissen, die wirklich gezeigt wurden, können wir den folgenden Rahmen nennen, den Dusart 1999 festgelegt hat:
Diese Methoden sind weit davon entfernt, genaue Formeln anzugeben. In diesem Rahmen wird beispielsweise nur behauptet, dass die tausendste Primzahl 7919 zwischen 7840 und 8341 liegt.
Trotz der vorstehenden Ausführungen ist es jedoch möglich, genaue Formeln von einfachem Aussehen zu erhalten, jedoch aufgrund zu langer Berechnungen ohne praktisches Interesse.
Der Wilson-Satz macht es leicht zu zeigen, dass die Funktion f ( n ) = 2 + (2 ( n ) mod (? N + 1)) alle Primzahlen erzeugt und nur diese, wenn n alle positiven ganzen Zahlen durchläuft: f ( n ) = n + 1, wenn n + 1 Primzahl ist, und sonst f ( n ) = 2 .
Die Fakultät von n nimmt schnell Werte an, die viel zu groß sind, um in der Praxis verwendet werden zu können, aber die Verwendung der Modulo-Funktion (die wir schnell berechnen können) umgeht diese Schwierigkeit. Die einzigen bekannten Methoden zur Berechnung von f ( n ) erfordern jedoch etwa n Elementaroperationen. Darüber hinaus liefert diese Funktion nicht tatsächlich π ( n ) , sondern testet nur, ob n eine Primzahl ist oder nicht. Für diesen Test oder zur Berechnung von π ( n ) ist f daher viel ineffizienter als die Methode zur Division durch alle ganzen Zahlen kleiner oder gleich √ n (oder als das Sieb von Eratosthenes ). Die Methoden selbst sind viel langsamer als die derzeit besten bekannte Primalitätstests .
Andere Formeln, die direkt p n oder π ( n ) ergeben, können aus f konstruiert werden ; Wir haben also die ganzzahlige Funktion ⌊ ∙ ⌋ :
;;Diese Formeln sind jedoch noch weniger einfach zu verwenden als die mit f .
Ein anderer Ansatz, der vielversprechender ist und nicht den Satz von Wilson verwendet, besteht im Wesentlichen darin, das Eratosthenes-Sieb oder die daraus ableitbaren Formeln zu simulieren , wie beispielsweise die Einschluss-Ausschluss-Formel von Legendre; Es ist der Lieblingsplatz vieler Amateure, daher wurden die folgenden Formeln im Jahr 2000 von einem Spanischlehrer, SM Ruiz, festgelegt:
und
Beachten Sie die große Anzahl von Summierungen in diesen Formeln, was bedeutet, dass auch sie in der Praxis nicht sehr nützlich wären. Viel bessere Methoden zur exakten Berechnung von π ( n ) und p n , die wir in dem Artikel über diese Funktionen ausführlich finden , bleiben relativ ineffizient.
Unter Berücksichtigung der Bemerkungen des ersten Abschnitts schien es unwahrscheinlich , dass Polynome mit mehreren Variablen existieren, die nur Primwerte verwenden. Auch die Arbeit von Matiyasevich, der 1970 das zehnte Problem von Hilbert löste, indem er zeigte, dass jede diophantinische Beziehung durch ein solches Polynom kodiert werden kann, sorgte für eine echte Überraschung. Es ist sogar möglich, explizite Beispiele für dieses Ergebnis zu nennen. somit das folgende monströse Polynom (Grad 25 und bestehend aus 26 Variablen):
mit
a, für eine Menge streng positiver Werte (wann ) genau die Menge der Primzahlen.
Man kann sich aber fragen, ob es hier wirklich wieder eine "Formel" gibt. Es ist auch äußerst schwierig, einen Satz von 26 Variablen zu finden, die eine positive Zahl ergeben, und es ist keine andere Methode zum Lösen eines solchen Systems bekannt, als alle möglichen Kombinationen der Parameter zu untersuchen.
Obwohl wir nicht genau von einer Formel sprechen können, bleibt eine Sequenz interessant , die durch eine Beziehung der Form u n + 1 = f ( u n ) definiert ist , wobei f eine ziemlich einfache Funktion ist und nur Primwerte annehmen würde. Bestimmte Sequenzen, die aus Euklids Beweis der Unendlichkeit von Primzahlen abgeleitet wurden (wie Sylvesters Sequenz ), erweisen sich in dieser Hinsicht als enttäuschend, so dass wir nicht einmal wissen, ob es eine Unendlichkeit von Primzahlen gibt . Wir kennen tatsächlich nur wenige interessante Beispiele für solche Sequenzen, außerdem eine etwas komplexere Form.
FRACTRAN-AlgorithmusConway definierte daher eine Verallgemeinerung des Syrakus-Problems , die es in eine Programmiersprache, FRACTRAN , umwandelt . der folgende Text:
entspricht für diese Sprache einem Programm, das in der Reihenfolge die Folge von Primzahlen erzeugt (wir können sie daher als eine durch Induktion definierte Folge interpretieren); Da die Wirksamkeit dieses Programms äußerst schwach ist, besteht das Interesse nur an der Eleganz seines Schreibens.
Rowlands SuiteDie durch die Wiederholungsrelation definierte Sequenz u n
(wobei gcd ( x , y ) die GCD von x und y bezeichnet ) und u n = a n + 1 - a n beginnt mit 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3 , 1, 1, ... (Fortsetzung A132199 des OEIS ). Rowland hat 2008 gezeigt, dass diese Sequenz (abgesehen von 1) nur Primzahlen enthält.
Sequenzen abhängig von einer reellen Zahl Mühlenformel1947 zeigte William H. Mills, dass es reelle Zahlen M gibt, so dass für jede ganze Zahl n der ganzzahlige Teil von M (3 n ) eine Primzahl ist. Das kleinste M mit dieser Eigenschaft, die Mills-Konstante , ist ebenfalls mit guter Genauigkeit bekannt, was sich jedoch als ebenso illusorisch für die Berechnung großer Primzahlen herausstellt, beispielsweise weil die Größe von p ( n ) = ⌊ M (3 n ) ist. ⌋ wird schnell viel größer als alles, was ein Computer aufnehmen kann (zum Speichern von p (25) benötigen Sie bereits ein Terabyte ).
Fridman SuiteIm Jahr 2017 haben Fridman et al. haben gezeigt, dass die Folge von Real ( f n ) definiert ist durch:
geprüft:
.Das irrationale f 1 = 2.9200509773… ist nichts anderes als der Mittelwert der Sequenz 2, 3, 2, 3, 2, 5 usw. dessen n- ter Term die kleinste Primzahl ist, die n nicht teilt .
Obwohl die entsprechenden Berechnungen leichter zu handhaben sind als die der Mills-Formel, bleibt dieses Ergebnis ebenso theoretisch. Tatsächlich erfordern diese Berechnungen die Kenntnis einer zunehmenden Anzahl von Dezimalstellen von f 1 (ungefähr n Dezimalstellen, um p n zu erhalten ) , aber um n Dezimalstellen von f 1 zu erhalten , müssen wir bereits die Werte der ersten n Primzahlen kennen . Auf der anderen Seite bietet dies eine Speicherkomprimierung. Tatsächlich erfordert das Speichern von Dezimalstellen weniger Speicher als für die ersten Primzahlen.
Kontinuierliche FraktionDas Konzept der kontinuierlichen Fraktion, das verwendet wird, um die positive reelle Zahl A064442 zu definieren, aus der wir die Folge von Primzahlen unter Verwendung der folgenden Wiederholung finden : . Daraus folgt .
Das Verfahren von Fridman et al. kann als Alternative zur kontinuierlichen Bruchmethode (zuvor bekannt) angesehen werden, und wir können daher den gleichen Vorbehalt machen: Die Zahl wird (oben) unter Verwendung von Primzahlen definiert, daher benötigen wir für diese Methode zunächst eine von Zahlen unabhängige alternative Definition sein verwendbar .
(en) Eric W. Weisstein , „ Prime Formulas “ , auf MathWorld