Odlyzko's method

Odlyzko [O1993] has a method for computing [math]\displaystyle{ \pi(x) }[/math] in time/space [math]\displaystyle{ x^{1/2+o(1)} }[/math]; combining this with a binary search, one can locate a k-digit prime in time/space [math]\displaystyle{ (10^k)^{1/2+o(1)} }[/math].

First observe that it suffices to compute [math]\displaystyle{ \pi(x) }[/math] to accuracy 1/2, since it is an integer. Next, it suffices to count the slight variant sum [math]\displaystyle{ \sum_{n \leq x} \frac{\Lambda(n)}{\log n} }[/math] up to this accuracy, since the error term is a sum over prime powers and this can be computed in [math]\displaystyle{ x^{1/2+o(1)} }[/math] time/space (using e.g. the sieve of Eratosthenes to find all the primes up to [math]\displaystyle{ x^{1/2} }[/math]).

In fact, it suffices to compute the sum

[math]\displaystyle{ \sum_{n} c(n) \frac{\Lambda(n)}{\log n} }[/math] (1)

where c is a computable function which equals 1 for [math]\displaystyle{ n \lt x - x^{1/2} }[/math], vanishes for [math]\displaystyle{ n\gt x }[/math], and is smooth in between. This is because the error can be computed in [math]\displaystyle{ x^{1/2+o(1)} }[/math] time/space via another sieve of Erathosthenes. [Actually, by using Odlyzko's method recursively, one can reduce this portion of the cost to [math]\displaystyle{ x^{1/4+o(1)} }[/math].]

The expression (1) can be rewritten using the zeta function as

[math]\displaystyle{ \frac{1}{2\pi i} \int_{2-i\infty}^{2+i\infty} F(s) \log \zeta(s)\ ds }[/math]

where

[math]\displaystyle{ c(u) = \frac{1}{2\pi i } \int_{2-i\infty}^{2+i\infty} F(s) u^{-s}\ du }[/math].

It turns out that F is rapidly decreasing when [math]\displaystyle{ Im(s) \gg x^{1/2} }[/math], so to get within accuracy 1/2, one only needs to evaluate the integral for [math]\displaystyle{ s = O(x^{1/2+o(1)}) }[/math]. By quadrature, this reduces to evaluating [math]\displaystyle{ \zeta(s) }[/math] (and its first few derivatives) to accuracy about [math]\displaystyle{ O(x^{-1/2+o(1)}) }[/math] for about [math]\displaystyle{ x^{1/2+o(1)} }[/math] values of s in this range, but this can be done in many ways (e.g. by the Euler-Maclaurin formulae).