An effective analytic recurrence for prime numbers

Basic Information

• Paper ID: 2508.02690
• Title: An effective analytic recurrence for prime numbers
• Author: Benoit Cloitre
• Classification: math.NT (Number Theory), math.HO (History and Overview)
• Publication Date: October 12, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2508.02690v2

Abstract

The Golomb-Keller formula expresses the next prime $p_{n+1}$ as a recurrence relation in terms of the first $n$ primes $p_1, \ldots, p_n$ through the Riemann ζ function and Euler products, but requires taking the limit $s \to \infty$, making it non-constructive. This paper transforms this asymptotic formula into an effective recurrence by proving that a finite parameter $s \leq p_n$ combined with the ceiling function is sufficient, establishing a constructive method valid for all $n \geq 1$.

The minimal integer parameter $s_n$ (OEIS A389650) reveals deep connections with prime constellations. The author unconditionally proves that $\liminf_{n\to\infty} \sigma_n = 0$, where $\sigma_n = s_n/p_n$. The limit superior $C = \limsup \sigma_n$ satisfies $\log \psi \lesssim C \leq 0.4332$, where $\psi \approx 1.46557$ is the super-golden ratio. The lower bound depends on the twin prime conjecture; the upper bound is unconditional. The constant $C$ relates to the densest admissible prime constellations, connecting to the Hardy-Littlewood conjecture.

The method extends to Dirichlet L-functions, yielding alternative effective formulas for computing $p_{n+1}$ and enabling prediction of $p_{n+1}$ modulo arbitrary integers with reduced precision requirements.

Research Background and Motivation

Problem Background

Finding explicit formulas for primes is a classical problem in number theory. While direct non-recursive formulas exist (such as Willans' formula, Mills' formula), they are computationally infeasible. This paper focuses on recurrence relations, namely expressing $p_{n+1}$ in terms of $p_1, \ldots, p_n$.

Historical Development

• Gandhi 4 first provided such recurrences using primorials and the Möbius function
• Vanden Eynden 19 simplified the proofs
• Jakimczuk 9 generalized the methods
• Golomb 5 independently discovered the formula using analytic number theory, later rediscovered by Keller 10

Limitations of Existing Methods

The classical Golomb-Keller formula is: $p_{n+1} = \lim_{s\to\infty} \left[\left(\prod_{k=1}^n \left(1-\frac{1}{p_k^s}\right)\right) \zeta(s) - 1\right]^{-1/s}$

The main problem with this formula is the requirement to take the limit $s \to \infty$, making it impractical for actual computation.

Research Motivation

This paper adopts the opposite approach: retain the complete ζ function series computation to working precision, but use a finite $s$. This truncates the exponent rather than the series, making the formula constructive.

Core Contributions

1. Constructive Recurrence Formula: Proves that for all $n \geq 1$, there exists a minimal integer $s_n$ such that: $p_{n+1} = \left\lceil \left(-1 + \zeta(s_n) \prod_{j=1}^n \left(1-\frac{1}{p_j^{s_n}}\right)\right)^{-1/s_n} \right\rceil$
2. Effective Bounds:
   • Proves $s_n \leq 2p_n$ using Bertrand's postulate (Theorem 10)
   • Proves $s_n \leq p_n$ using Nagura's theorem (Theorem 12)
3. Asymptotic Behavior Analysis:
   • Unconditionally proves $\liminf_{n\to\infty} \sigma_n = 0$ (Proposition 13)
   • Establishes bounds for $C := \limsup_{n\to\infty} \sigma_n$: $0.3823 \lesssim C \leq 0.4332$
4. Connection with Prime Constellations: Discovers the lower bound $\log \psi \approx 0.3823$ (dependent on the twin prime conjecture), where $\psi$ is the super-golden ratio
5. Extension to Dirichlet L-functions: Enables prediction of residue properties such as $p_{n+1} \pmod 4$
6. Numerical Data: Provides values of $s_n$ for $n = 1$ to $200$ (OEIS A389650)

Detailed Methodology

Problem Formulation

Given the first $n$ primes $p_1, p_2, \ldots, p_n$, constructively compute the next prime $p_{n+1}$.

Core Methodological Framework

1. Dirichlet Series Mechanism

Define the key function: $D_n(s) = \sum_{\substack{k \geq 1 \\ \gcd(k,P_n)=1}} k^{-s}$

where $P_n = \prod_{j=1}^n p_j$ is the $n$-th primorial.

2. Euler Product Representation

Lemma 3: For $\Re(s) > 1$, $D_n(s) = \zeta(s) \prod_{j=1}^n (1-p_j^{-s})$

3. Convergence Properties Analysis

Define $h(s) = (D_n(s)-1)^{-1/s}$, proving:

• $h(s) < p_{n+1}$ for all $s > 1$
• $\lim_{s\to\infty} h(s) = p_{n+1}$
• $h(s)$ is strictly increasing on $(1,\infty)$

4. Critical Parameter Determination

Proposition 6: For each $n \geq 1$, there exists a unique $s_n^* > 1$ such that $h(s_n^*) = p_{n+1} - 1$.

Define $s_n = \lfloor s_n^* \rfloor + 1$ as the minimal integer parameter.

Technical Innovations

1. Precision-Truncation Trade-off: Unlike Keller's approach of truncating series summation, this paper retains the complete ζ function but uses finite $s$
2. Ceiling Function Technique: Cleverly exploits the property that $\lceil h(s) \rceil = p_{n+1}$ if and only if $s > s_n^*$
3. Integral Bound Techniques: Uses refined integral comparisons to control tail error terms

Experimental Setup

Numerical Computation Tools

• High-precision computation using PARI/GP and Python's mpmath library
• 100-digit precision required for $n \leq 200$
• Approximately 2500-digit precision needed for $n \approx 500$ (due to enhanced cancellation effects)

Verification Methods

Theoretical bounds $s_n \leq p_n$ are verified by direct computation for all $n = 1, \ldots, 200$.

Working Example

Computing $p_7 = 17$ (starting from $n = 6$):

• Using $s = 2p_6 = 26$: $h(26) \approx 16.941817904$, yielding $p_7 = \lceil h(26) \rceil = 17$
• Actual minimum value $s_6 = 8$: $h(8) \approx 16.5189076$

Experimental Results

Main Numerical Results

Bound Verification

• Theorem 10: $s_n \leq 2p_n$ holds for all $n \geq 1$
• Theorem 12: $s_n \leq p_n$ holds for all $n \geq 1$ (via Nagura's theorem)

Asymptotic Behavior

• Proposition 13: $\liminf_{n\to\infty} \sigma_n = 0$ (unconditional)
• Theorem 14: $C = \limsup_{n\to\infty} \sigma_n \leq 0.4332$ (unconditional)
• Theorem 15: Under the twin prime conjecture, $C > \log \psi \approx 0.38225$

Empirical Distribution Analysis

Analysis of data for $n = 1$ to $200$ shows:

• After removing five outliers, the distribution of $\sigma_n$ resembles a Beta distribution
• Mean ≈ 0.291, median ≈ 0.277, standard deviation ≈ 0.087
• Fitted parameters: Beta(α ≈ 7.64, β ≈ 18.62)
• Theoretical mode ≈ 0.274, consistent with empirical median

Fixed Coefficient Formula

Theorem 18: For any $c > c_0 \approx 0.5956$, there exists $N_0(c)$ such that for all $n \geq N_0(c)$, the formula using $s = cp_n$ correctly computes $p_{n+1}$.

Related Work

Historical Development Timeline

1. Gandhi (1971): First recurrence using primorials and Möbius function
2. Golomb (1976): Introduction of analytic number theory methods
3. Keller (2007): Independent rediscovery with alternative derivation
4. This paper (2025): First to make the formula constructive

Comparison with Other Methods

• Willans' formula: Direct but computationally infeasible
• Mills' formula: Based on a constant but requires prior knowledge of primes
• Sieve methods: Practical but do not provide recurrence structure
• This method: Theoretically interesting but computationally complex

Conclusions and Discussion

Main Conclusions

1. Constructive Breakthrough: First transformation of the Golomb-Keller formula from asymptotic to effectively computable
2. Deep Connections: Reveals intrinsic relationships between prime recurrence parameters and prime constellations, gap distributions
3. Theoretical Bounds: Establishes precise bounds and asymptotic behavior of parameter $s_n$
4. Super-Golden Ratio: Discovers new applications of this constant in prime theory

Limitations

1. Computational Complexity: $O(np_n^3 \log p_n)$ bit operations—polynomial but practically infeasible
2. Precision Requirements: Exponential growth in working precision needed as $n$ increases
3. Conditional Results: Some important results depend on unproven conjectures (e.g., twin prime conjecture)

Future Directions

1. Computational Optimization: Seek methods to reduce precision requirements
2. Theoretical Refinement: Remove dependence on unproven conjectures
3. Generalization: Extend to other number-theoretic functions
4. Numerical Exploration: Compute $s_n$ values over larger ranges to verify conjectures

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Successfully resolves a long-standing constructivity problem
2. Rigorous Methodology: Employs sophisticated analytic number theory techniques
3. Deep Connections: Bridges recurrence formulas and prime constellation theory
4. Rich Data: Provides detailed numerical verification and statistical analysis

Weaknesses

1. Limited Practical Utility: While theoretically constructive, computational cost is prohibitive
2. Precision Challenges: High precision requirements limit method scalability
3. Conditional Results: Some important results depend on unproven conjectures

Impact

1. Theoretical Contribution: Provides new perspectives on prime recurrence theory
2. Methodological Value: Demonstrates how to convert asymptotic formulas into effective algorithms
3. Interdisciplinary Connections: Links analytic number theory, computational number theory, and prime geometry

Applicable Scenarios

1. Theoretical Research: Prime distribution, gap theory, constellation studies
2. Numerical Experiments: Small-scale verification and pattern exploration
3. Educational Demonstration: Classic applications of analytic number theory methods

References

Key references include:

• 5 S. W. Golomb, Formulas for the next prime, Pacific J. Math. 63 (1976), 401–404
• 10 J. B. Keller, A recursion equation for prime numbers, arXiv:0711.3940, 2007
• 4 J. M. Gandhi, Formulae for the nth prime, Proc. Washington State Univ. Conf. Number Theory (1971), 96–107
• 12 J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), 177–181

This paper holds significant theoretical importance in number theory. While its practical computational applications are limited, its theoretical insights and methodological innovations open new directions for prime theory research. Particularly noteworthy are the discovered connections with the super-golden ratio and prime constellations, revealing unexpected deep structures in number theory.