Optimierung einer expliziten, deterministischen Formel für alle Primzahlen

DIE PRIMZAHLENSERIE

Beitrag 30

In der vorliegenden Arbeit wird eine explizite, deterministische Formel zur Berechnung der Primzahlen weiterentwickelt und algorithmisch optimiert. Ausgangspunkt ist eine exakte mathematische Konstruktion, deren innere Struktur unverändert bleibt, deren praktische Auswertbarkeit jedoch entscheidend verbessert wird.

In Beitrag 29 wurde dieselbe exakte Primzahlformel unter Verwendung empirischer Schranken vorgestellt. Für diese Version ist die garantierte Gültigkeit formal auf

$i\le 99\,980$

beschränkt. Der mathematische Kern der Formel ist dabei vollständig korrekt; die Einschränkung betrifft ausschließlich die Wahl der verwendeten Schranken.

Im vorliegenden Beitrag werden daher ausschließlich bewiesene explizite Schranken eingesetzt. Dadurch wird dieselbe Formel zu einer für alle natürlichen Zahlen $i>2$ gültigen, vollständig garantierten Berechnungsvorschrift für die i-te Primzahl $p_i$ .

Explizite Primzahlformel (optimierte Form)

Eine explizite Formel für die i-te Primzahl ist gegeben durch

$p_i = 2m(i)-1 + 2\sum_{n_{\max}=m(i)-2}^{u(i)} \left\lfloor \left( \frac{i}{\pi(1,n_{\max})+3} \right)^{1/i} \right\rfloor,$

gültig für $i>3$ und $i\in\mathbb{N}$ ,

wobei

$p_1=2,\qquad p_2=3,\qquad p_3=5$

als bekannt vorausgesetzt werden.

Explizite Schranken und ihre Herkunft

Für die praktische Auswertung werden Funktionen $m(i)$ und $u(i)$ verwendet, so dass stets gilt

$2m(i)-1 < p_i < 2u(i)+1.$

Untere Schranke (Dusart, 2010)

Für alle $i\ge6$ gilt die bewiesene Abschätzung

$p_i > i(\ln i+\ln\ln i-1),$

und für alle $i\ge688\,383$ die verschärfte Abschätzung

$p_i > i\left( \ln i+\ln\ln i-1+\frac{\ln\ln i-2.1}{\ln i} \right).$

Aus diesen Abschätzungen wird eine ganzzahlige Indexfunktion $m(i)$ definiert, die keinen Primzahlindex darstellt, sondern den Index eines ungeraden Kandidaten der Form $2n+1$ , der garantiert links von $p_i$ liegt:

$m(i)= \begin{cases} 2, & i=3,\\ 3, & i=4,\\ 5, & i=5,\\[6pt] \left\lfloor \dfrac12\,i(\ln i+\ln\ln i-1) \right\rfloor, & 6\le i<688\,383,\\[10pt] \left\lfloor \dfrac12\,i\left( \ln i+\ln\ln i-1+\dfrac{\ln\ln i-2.1}{\ln i} \right) \right\rfloor, & i\ge688\,383. \end{cases}$

Damit gilt für alle $i\ge3$ stets

$2m(i)-1 < p_i.$

Obere Schranke (Axler, 2017/2019)

Für hinreichend große $i$ gilt die bewiesene Abschätzung

$p_i < i(\ln i+\ln\ln i).$

Hieraus wird gesetzt

$u(i)=\left\lceil\dfrac12\,i(\ln i+\ln\ln i)\right\rceil.$

Algorithmische Optimierung

Die innere Summe der Formel wird inkrementell fortgeschrieben. Die äußere Summation kann abgebrochen werden, sobald der ganzzahlige Summand erstmals den Wert Null annimmt, äquivalent zur Bedingung $\pi(1,n)+3>i$ .

Die erste Nullstelle

$n_{\max}=\min\{n:\pi(1,n)+3>i\}$

liefert direkt

$p_i = 2n_{\max}+3.$

Numerische Validierung und Skalierungsverhalten

Die Berechnungen wurden in wxMaxima auf einem
HP Pavilion Laptop 15-cs2xxx durchgeführt.

$\begin{alignedat}{4} i=10^2 \;&:\quad & p_i &= 541, \quad & \text{Laufzeit }&0.03\,\mathrm{s}, \quad & \text{Speicher }&4.7\,\mathrm{MB} \\[2pt] i=10^3 \;&:\quad & p_i &= 7919, \quad & \text{Laufzeit }&0.72\,\mathrm{s}, \quad & \text{Speicher }&120\,\mathrm{MB} \\[2pt] i=10^4 \;&:\quad & p_i &= 104729, \quad & \text{Laufzeit }&20.3\,\mathrm{s}, \quad & \text{Speicher }&4.0\,\mathrm{GB} \\[2pt] i=10^5 \;&:\quad & p_i &= 1299709, \quad & \text{Laufzeit }&732\,\mathrm{s}, \quad & \text{Speicher }&132\,\mathrm{GB} \\[6pt] i=10^6 \;&:\quad & p_i &= 15\,485\,863, \quad & \text{Laufzeit }&26\,600\,\mathrm{s}, \quad & \text{Speicher }&4.5\,\mathrm{TB} \end{alignedat}$

Die millionste Primzahl

$\boxed{p_{10^6}=15\,485\,863}$

stimmt exakt mit dem bekannten Referenzwert überein. Damit ist die formale Korrektheit der optimierten expliziten Primzahlformel auch für große Ordnungszahlen numerisch bestätigt.

Fazit

Die vorliegende Arbeit zeigt, dass eine exakte, deterministische Primzahlformel durch den Einsatz bewiesener Schranken und eine inkrementelle Auswertungsstrategie formal korrekt und bis in große Ordnungszahlen hinein anwendbar ist. Der erhebliche Rechenaufwand unterstreicht dabei den konzeptionellen Charakter der Konstruktion als explizite mathematische Beschreibung der Primzahlenfolge, nicht als praktisch effizientes Hochleistungsverfahren.

Danksagung

Der Autor dankt Eratosthenes, Euklid, Carl Friedrich Gauß, Georg Cantor, Hugh Willans, Pierre Dusart und Christian Axler für ihre grundlegenden Beiträge zur Theorie und Struktur der Primzahlen.

München, 23. Dezember 2025

Gottfried Färberböck

Sprache:

Sprache:

DIE PRIMZAHLENSERIE

Optimierung einer expliziten, deterministischen Formel für alle Primzahlen