Optimization of an Explicit, Deterministic Formula for All Prime Numbers

THE PRIME NUMBER SERIES 30

In THE PRIME NUMBER SERIES 29, an explicit, deterministic formula was presented which yields exactly the i-th prime number $p_i$ for every natural number $i > 2$ . The formula operates exclusively with elementary arithmetic operations, integer-valued functions, as well as finite sums and products, and generates the prime numbers strictly ordered along the number line.

However, as the index i increases, the computational effort required for direct evaluation grows rapidly. In the present post, it is shown that the very same formula — without any mathematical modification — can be accelerated by several orders of magnitude through a suitable algorithmic evaluation strategy. The core of the improvement lies in the use of proven explicit bounds for $p_i$ and in an incremental evaluation of the inner summation structure.

Explicit Prime Number Formula

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

$p_{i}=2m(i)-1+2*\sum\limits_{n_{max}=m(i)-2}^{u(i)}(\lfloor(\frac{i}{\sum\limits_{n=1}^{n_{max}}(\prod\limits_{k=0}^{\frac{\sqrt{2n+3}-3}{2}}(\lceil1-\frac{k+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3)}{n}\rceil))+3})^\frac{1}{i})\rfloor)$

valid for $i > 2 \wedge i \in \mathbb{N}$ ,

where

$p_{1}=2$

and

$p_{2}=3$

are assumed to be known.

Explicit Bounds and Their Origin

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

$2m(i)-1 < p_{i} < 2u(i)+1$

always holds.

Lower Bound (Dusart, 2010)

For sufficiently large i, the following proven estimate applies:

$p_{i}>i(\ln i+\ln\ln i-1+\frac{\ln\ln i-2}{\ln i})$

This motivates the definition

$m(i)=\lfloor\frac{1}{2}i(\ln i+\ln\ln i-1+\frac{\ln\ln i-2}{\ln i})\rfloor$

Source:
Pierre Dusart, *Estimates of Some Functions Over Primes without R.H.*, 2010.

Upper Bound (Axler, 2017/2019)

For sufficiently large i, the following proven explicit estimate holds:

$p_{i}<i(\ln i+\ln\ln i)$

Hence, we define

$u(i)=\lceil\frac{1}{2}i(\ln i+\ln\ln i)\rceil$

Source:
Christian Axler, *New estimates for the n-th prime number*, 2017 / 2019.

Algorithmic Optimization

The decisive algorithmic improvement is based on the observation that the inner sum of the formula can be evaluated incrementally. The summation over n therefore does not need to be recomputed from scratch for each $n_{max}$ , but can be extended successively.

For this purpose, the inner summation structure is explicitly formulated as a separate function. Let

$\pi(n_{\min},n_{\max})=\sum_{n=n_{\min}}^{n_{\max}} t(n)$

with

$t(n)=\prod_{k=0}^{k_{\max}} \left\lceil 1-\frac{k+\left\lfloor\frac{n-k}{2k+3}\right\rfloor(2k+3)}{n} \right\rceil$

and

$k_{\max}=\left\lfloor\frac{\left|\sqrt{2n+3}-3\right|}{2}\right\rfloor,$

where $n\in\mathbb{N},\,n\ge1$ and $k\in\mathbb{N}_0$ .

In particular, this implies

$\sum_{n=1}^{n_{\max}} \left( \prod_{k=0}^{\left\lfloor\frac{\left|\sqrt{2n+3}-3\right|}{2}\right\rfloor} \left\lceil 1-\frac{k+\left\lfloor\frac{n-k}{2k+3}\right\rfloor(2k+3)}{n} \right\rceil \right) =\pi(1,n_{\max})$

where the function $\pi$ can be incrementally updated according to

$\pi(1,n_{\max})=\pi(1,n_{\max}-1)+t(n_{\max}).$

With this notation, the explicit prime number formula can equivalently be written in compact form as

$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)^{\frac{1}{i}} \right\rfloor.$

Furthermore, it turns out that the formal upper bound $u(i)$ is usually not fully exhausted in practical evaluation. Once the integer summand attains the value zero for the first time, all subsequent summands contribute nothing further to the result. The effective upper limit thus emerges dynamically during computation.

Examples (Exact Results)

$p_{3}=5$

$p_{4}=7$

$p_{60}=281$

$p_{100}=541$

$p_{200}=1223$

$p_{1000}=7919$

$p_{5000}=48611$

$p_{10000}=104729$

$p_{100000}=1299709$

Empirical Observation:
While a naive direct evaluation becomes extremely time-consuming for large indices, the optimized evaluation using explicit bounds reduces computation time by several orders of magnitude (e.g., from approximately 37.5 hours to under two minutes for $p_{10000}$ ). By terminating the outer summation at the moment when the integer summand first attains the value zero, the computation time required to determine the 10,000th prime number $p_{10000}$ ) was reduced to approximately 31 seconds.

Acknowledgments

The author thanks Eratosthenes, Euclid, Carl Friedrich Gauss, Georg Cantor, and Hugh Willans for their fundamental contributions to the theory and structure of prime numbers.

Note on the Origin

During the technical review and algorithmic refinement of the evaluation strategy, ChatGPT was used as a supporting tool. The mathematical core idea, the structure of the formula, and the conceptual objective originate from the author.

Munich, December 23, 2025

Gottfried Färberböck

Language:

Language:

THE PRIME NUMBER SERIES

Optimization of an Explicit, Deterministic Formula for All Prime Numbers