12
$\begingroup$

The prime counting function $\pi(x)$ has been determined for $x=10^{26}$.

The list of the $10^n$-th primes , however , ends at $n=18$. The $10^{18}$-th prime has $20$ digits.

Apparantly, the determination of $\pi(x)$ is easier than the determination of $p_n$ (the $n$-th prime).

What is the computational complexity of determining $\pi(n)$ exactly ?

What is the computational complexity of determining the $n$-th prime ?

Is the second problem actually harder than the first ? (I think this is not the case because with binary search, it should be possible to determine $p_n$ nearly as efficiently as the determination of $\pi(n)$)

It is true that the problem is not of great practical interest because $li(x)$ is a very good approximation of $\pi(x)$. I am just curious how far the exact calculation could go on with the current computational power available.

$\endgroup$
7
  • $\begingroup$ see Lagarias-Odlyzko's algorithm for computing $\pi(x)$. and you are right, with binary search, computing the $n$th prime is $\Theta(\log_2(n) K(n \log n))$ where $K(x)$ is the complexity of computing $\pi(x)$ $\endgroup$
    – reuns
    Commented Jul 20, 2016 at 19:06
  • $\begingroup$ The nth prime computation is a relatively small amount more work, albeit the $n$ using corresponds to approx $n\log n$ for the count, which explains some of the discrepency. Rather than a binary search, we typically use R(x) or some other good estimate, do a single prime count, then sieve the difference. This works out best in practice. For theory. my guess is that the complexity of sieving using the $O(x^{1/2}\log x)$ RH bound on li(x) will come out smaller than the cost of log(n) applications of $O(x^{2/3}/\log x)$ LMO or extended LMO. $\endgroup$
    – DanaJ
    Commented Jul 22, 2016 at 18:18
  • 1
    $\begingroup$ I should also point out that your data is old. $\pi(x)$ has been found for $x=10^{27}$, and $p_n$ for $n=10^{24}$. One reason is that Kim Walisch has been working hard the last couple years on his primecount (and primesieve and primesum) program, including expanding to 128 bits and adding support for MPI. In practice, a simple experiment on a 4770K: time for 10^17th prime, 1min57s. Time for $\pi(p_{10^{17}})$: 1min56s. The prime count time completely dominates, and we see that we wouldn't want to run it more than once. $\endgroup$
    – DanaJ
    Commented Jul 22, 2016 at 18:49
  • 1
    $\begingroup$ @DanaJ Nice, always good to see new results. Do you happen to know how the combinatorial method compares to the analytical method at these upper ranges? $\endgroup$
    – Deedlit
    Commented Jul 22, 2016 at 20:54
  • 1
    $\begingroup$ @Peter, nth prime at oeis.org/A006988 . Prime count at oeis.org/A006880. Announcement of result and later verification for 10^27 at mersenneforum.org/showthread.php?t=20473. $\endgroup$
    – DanaJ
    Commented Jul 23, 2016 at 4:56

2 Answers 2

Reset to default
7
$\begingroup$

Right now there are two competing methods for determining $\pi(x)$ when $x$ is large: the combinatorial method of Meissel-Lehmer-Lagarias-Miller-Odlyzko-Deleglise-Rivat (see here), which requires $O(\frac{x^{\frac{2}{3}}}{(\log x)^2})$ time and $O(x^{\frac{1}{3}}(\log x)^2)$ space, and the analytical method of Lagarias-Odlyzko (see here), which requires $O(x^{\frac{1}{2}+\epsilon})$ time and $O(x^{\frac{1}{4}+\epsilon})$ space. (Although actually, the latter method can be modified to require $O(x^{\frac{3-2\delta}{5}+\epsilon})$ time and $O(x^{\delta+\epsilon})$ space for $0 \le \delta \le \frac{1}{4}$.)

Interestingly, the record of $\pi(10^{26})$ was obtained using the combinatorial method, which is slower asymptotically; perhaps the crossover point has not yet been reached. Another factor is likely the difficulty of implementing the analytical method.

As you say, we can use $\pi(n)$ to determine $p_n$, and the computational complexities will not be much different asymptotically; however, the difference is likely enough to cause $p_n$ to lag behind, since we would need to evaluate $\pi(n)$ many times just to determine one value of $p_n$. But, I would say that the difference of a factor of $10^6$ between the two records is probably due to less attention paid to $p_n$.

$\endgroup$
2
$\begingroup$

According to Kim Walisch's benchmark Xavier Gourdon's method is the faster.

Its time complexity is $O(\frac{x^{\frac{2}{3}}}{(\log x)^2})$ which seems to be same as Deleglise-Rivat's, but performs better due to constant optimizations.

Time Complexity over time:

1798 : Legendre => $O(n^{3/4})$

1870 : Meissel => $O(n^{2/3}.log^{1/3}n)$

1959 : Lehmer => $O(n^{2/3})$ — popularly known as Missel-Lehmer

1985 : Lagarias, Miller and Odlyzko => $O(n^{2/3}/log\ n)$ — popularly known as LMO

1996 : M. Deleglise, J. Rivat => $O(n^{2/3}/log^2n)$

2001 : Xavier Gourdon => $O(n^{2/3} / log^2n)$ (constant factor for both time and memory improved) — default algo for Kimwalisch's package

2015 : Douglas Staple => $O(n^{2/3} / log^2n)$ (constant factor for memory improved)

$\endgroup$
1
  • $\begingroup$ Where did you get the complexities for Legendre, Meissel and Lehmer. Legendre's method is Omega(x) (his sum has that many terms). Meissel's is not clear, but Pomerance and Crandall state that his and Lehmer's are Omega(x). $\endgroup$
    – Victor Miller
    Commented Jan 16, 2023 at 19:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .