Optimization of an Explicit, Deterministic Formula for All Prime Numbers

THE PRIME NUMBER SERIES 30

In the present work, an explicit, deterministic formula for the computation of prime numbers is further developed and algorithmically optimized. The starting point is an exact mathematical construction whose internal structure remains unchanged, while its practical evaluability is decisively improved.

In Contribution 29, the same exact prime formula was presented using empirical bounds. For that version, the guaranteed validity is formally restricted to

$i\le 99\,980$

The mathematical core of the formula is entirely correct; the restriction concerns exclusively the choice of the bounds employed.

In the present contribution, only proven explicit bounds are used. As a result, the same formula becomes a fully guaranteed computational rule for the i-th prime number $p_i$ , valid for all natural numbers $i > 2$ .

Explicit Prime Formula (Optimized Form)

An explicit formula for the i-th prime number is given by

$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,$

valid for $i>3$ and $i\in\mathbb{N}$ ,

where

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

are assumed as known.

Explicit Bounds and Their Origin

For practical evaluation, functions $m (i)$ and $u (i)$ are used such that always

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

Lower Bound (Dusart, 2010)

For all $i\ge6$ , the proven estimate holds:

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

and for all $i\ge688\,383$ , the sharpened estimate holds:

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

From these estimates, an integer index function $m(i)$ is defined. It does not represent a prime index, but rather the index of an odd candidate of the form $2n+1$ that is guaranteed to lie to the left of $p_i$ :

$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}$

Thus, for all $i\ge3$ , it always holds that

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

Upper Bound (Axler, 2017/2019)

For sufficiently large $i$ , the proven estimate holds:

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

From this, we set

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

Algorithmic Optimization

The inner sum of the formula is evaluated incrementally. The outer summation can be terminated as soon as the integer summand first becomes zero, which is equivalent to the condition $\pi(1,n)+3>i$ .

The first zero position

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

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

liefert direkt

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

Numerical Validation and Scaling Behavior

The computations were performed in wxMaxima on an
HP Pavilion Laptop 15-cs2xxx.

$\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}$

The millionth prime number

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

agrees exactly with the known reference value. This numerically confirms the formal correctness of the optimized explicit prime formula even for large indices.

Conclusion

The present work shows that an exact, deterministic prime formula can be made formally correct and applicable up to large indices through the use of proven bounds and an incremental evaluation strategy. The substantial computational effort underscores the conceptual character of the construction as an explicit mathematical description of the prime sequence, rather than as a practically efficient high-performance method.

Munich, December 23, 2025

Gottfried Färberböck

Language:

Language:

THE PRIME NUMBER SERIES

Optimization of an Explicit, Deterministic Formula for All Prime Numbers

Explicit Prime Formula (Optimized Form)

Explicit Bounds and Their Origin

Upper Bound (Axler, 2017/2019)

Algorithmic Optimization

Numerical Validation and Scaling Behavior

Conclusion