A Note on Algorithms for Computing p n p_{n}

Ansh Aggarwal · 2025

Read A Note on Algorithms for Computing p n p_{n} by Ansh Aggarwal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16285.txt.

Introduction

Ansh Aggarwal, in a short solo note, compares algorithms for computing the nth prime number exactly. The core difficulty is inverting the prime-counting function, and he leverages known complexity results for evaluating that function to bound several strategies.

A binary search approach is shown to run in time growing like the square root of n times a modest power of log n. Assuming both the Riemann Hypothesis and Cramér's conjecture on prime gaps, he traps the answer in a tighter interval around the inverse logarithmic integral and improves the sieve-based bound slightly. Though that gain is conditional, it indicates that sharper prime-gap estimates would translate directly into provably faster prime computation.

Catalog record

CREATORAnsh Aggarwal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16285

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Note on Algorithms for Computing p n p_{n} Ansh Aggarwal Abstract We analyze algorithms for computing the n n th prime p n p_{n} and establish asymptotic bounds for several approaches. Using existing results on the complexity of evaluating the prime-counting function π ⁡ ( x ) \pi(x) , we show that the binary search approach computes p n p_{n} in O ⁡ ( n ​ ( log ⁡ n ) 4 ) O(\sqrt{n}\,(\log n)^{4}) time. Assuming the Riemann Hypothesis and Cramér’s conjecture, we construct a tighter interval around li − 1 ​ ( n ) \text{li}^{-1}(n) , leading to an improved sieve-based algorithm running in O ⁡ ( n ​ ( log 7 / 2 ⁡ n ) ​ log ⁡ log ⁡ n ) O(\sqrt{n}\,(\log^{7/2}n)\,\log\log n) time. This improvement, though conditional, suggests that further refinements to prime gap estimates may yield provably faster methods for computing primes. 1 Introduction Finding the n th prime, denoted p_{n} , given n is an important problem [ 2 ] . It is known that an oracle for \pi(x) , the prime counting function, allows one to simply run binary search to compute p_{n} with at most \log_{2}n calls to \pi(x) [ 2 ] . First, given recent developments, we present a simple analysis for the explicit run time for this binary search approach. Notably, we look at Pierre Dusart’s bounds for p_{n} [ 4 ] and look at the fastest known method of computing \pi(x) [ 7 ] . Here, we conclude that p_{n} can be found, given n , in O(\sqrt{n}\cdot\log^{4}n) time. Next, we consider sieving to find p_{n} . We show that the fastest sieve, which is a sublinear sieve [ 13 ] , cannot beat the binary search algorithm asymptotically. Instead, we consider a sieve that finds primes over an interval [R,L] using a segmented sieve. Ultimately, we show that for such a sieve to beat binary search, it must have an interval tighter than some B . A look at the literature tells us that an easy bound for p_{n} that is sufficiently tight does not exist. Finally, we assume the Riemann hypothesis and Cramér’s conjecture on prime gaps to show a way to construct an interval tight enough that an interval sieve would asymptotically beat binary search. Thus based on this result, we construct a new algorithm that beats binary search to find p_{n} given n . This algorithm runs in O(\sqrt{n}\cdot(\log^{7/2}n)\cdot\log\log n) time. In this document, \log refers taking logarithm with base e . We generally denote logarithms in big- O notation with \log . 2 Bounds for p_{n} In [ 4 ] , Pierre Dusart provides bounds for p_{n} , namely, for n\geq 6 : \displaystyle L=n(\log n+\log(\log n)-1)<p_{n}<n(\log n+\log(\log n))=R (1) This has the immediate consequence that p_{n} is always contained in interval of size n . Corollary 2.1 . R-L=n(\log n+\log(\log n))-n(\log n+\log(\log n)-1)=n For n\geq 688383 , Dusart gives a more refined interval of size \frac{n}{10\cdot\log n} . However, since we hope to use this interval with binary search, we show that this improvement does not yield an asymptotic improvement for computing p_{n} . Lemma 2.2 . Improving the search interval for binary search by a \log factor does not improve the asymptotic run time. Proof. We want to show O(\log n)=O(\log(n/\log n)) . Consider the following limit: \displaystyle\lim_{n\to\infty}\frac{\log(n/\log n)}{\log n}=\lim_{n\to\infty}\frac{\log n}{\log n}-\lim_{n\to\infty}\frac{\log\log n}{\log n}=1-0=1 (2) Thus, under binary search, the bounds for p_{n} give the same asymptotic result. ∎ 3 Using \pi(x) to Compute p_{n} The prime counting function, \pi(x) , returns the number of prime numbers smaller than or equal to x . Formally, this may be written [ 2 ] as: \displaystyle\pi(x)=\sum_{p\leq x}1 (3) This, however, is not an efficient method to compute \pi(x) . Instead, there are two major efficient approaches to computing \pi(x) , both of which, in their best forms, run in \tilde{O}(\sqrt{x}) time. In [ 9 ] , Lagarias and Odlyzko present an analytic method to compute \pi(x) , assuming the Riemann hypothesis holds true however, the authors note that despite its asymptotic result, it might be impractical to use due to the implied constants, leaving the combinatorial approach as the only real option. In [ 7 ] , Hirsch, Kessler, and Mendlovic improve to \tilde{O}(\sqrt{x}) , explicitly O(\sqrt{x}\cdot(\log x)^{5/2}) due to proposition 16 in their paper, with previous notable results attributed Lagarias, Miller, and Oldyzko [ 8 ] and Rivat and Deléglise [ 3 ] . In [ 2 ] , the authors prove that p_{n} can be computed quickly given an oracle for \pi(x) using binary search. This is done by finding the smallest x such that \pi(x)=n because all x^{\prime}>x such that \pi(x^{\prime})=n are necessarily composite. Let T_{\pi} denote the time complexity of evaluating \pi(x) . Theorem 3.1 . Using an oracle for \pi(x) , the n th prime is computed in O(T_{\pi}\log n) time. Proof. From Section 2 , [L,R] defines an interval that contains p_{n} and it suffices to run binary search over it. The length of the interval is n\implies up to \log_{2}n evaluations of \pi(x) are required, thus we have O(T_{\pi}\log n) time. Remark: The change of base from \log_{2} to \log is allowed as it does not affect the asymptotic result but allows for cleaner simplifications in the proofs that follow ∎ Thus, using the algorithm from [ 7 ] , we obtain a more refined result. Lemma 3.2 . We can compute p_{n} in O(\sqrt{n}\cdot(\log n)^{4}) time. Proof. Using the Prime Number Theorem, it is trivial to note that O(\sqrt{x}\cdot(\log x)^{5/2})\sim O(\sqrt{n\log n}\cdot(\log(n\log n))^{5/2})=T_{\pi} thus we have: \displaystyle O(\sqrt{n\log n}\cdot(\log(n\log n))^{5/2}) (4) \displaystyle\implies T_{\pi}=O(\sqrt{n}\cdot(\log n)^{3}) (5) Following Theorem 3.1 , we conclude that p_{n} is computed in O(\sqrt{n}\cdot(\log n)^{3}\cdot\log n)\implies O(\sqrt{n}\cdot(\log n)^{4}) . ∎ 4 Sublinear Sieves In [ 13 ] , Sorenson presented a sublinear sieve that built on Pritchard’s work in [ 10 , 11 ] . A sieve produces all primes up to some bound M ; thus, to compute p_{n} , it suffices to sieve up to an upper bound, like R from Section 2.1 and counting to n th number in the list. With R as the upper bound, the sublinear sieve runs in O(R/\log\log R) time. Lemma 4.1 . A sublinear sieve takes O((n\log n)/\log\log n) time to compute p_{n} . Proof. From Section 2 , R=n(\log n+\log(\log n)) gives: \displaystyle O\left(\frac{n(\log n+\log(\log n))}{\log(\log n(\log n+\log(\log n)))}\right)\implies O\left(\frac{n\log n}{\log(\log n(\log n+\log(\log n)))}\right) (6) Let T denote the expression on the right. Note that: \displaystyle T\subseteq O\left(\frac{n\log n}{\log\log n}\right) (7) Counting once sieving is completed takes O(n) time thus, we have O((n\log n)/\log\log n) . ∎ Theorem 4.2 . A sublinear sieve is asymptotically worse than the binary search algorithm to compute p_{n} . Proof. The theorem is true if the following limit converges to 0 : \displaystyle\lim_{n\to\infty}\sqrt{n}\cdot(\log n)^{4}\cdot\frac{\log\log n}{n\log n}=\lim_{n\to\infty}\frac{(\log n)^{3}(\log\log n)}{\sqrt{n}} (8) Note that \displaystyle\frac{(\log n)^{3}(\log\log n)}{\sqrt{n}}\leq\frac{(\log n)^{3}}{\sqrt{n}} (9) Thus, if the latter expression converges, so does the original limit, \displaystyle\lim_{n\to\infty}\frac{(\log n)^{3}}{n^{1/2}}=0 (10) We conclude that this converges to 0 by a few applications of L’Hopital’s rule. ∎ 5 Further Sieving Troubles Another way to find p_{n} is to sieve over a sufficiently small range [i,j] with

Read the complete text