View source for Odlyzko's method

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

First observe that it suffices to compute <math>\pi(x)</math> to accuracy 1/2, since it is an integer.  Next, it suffices to count the slight variant sum <math>\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>x^{1/2+o(1)}</math> time/space (using e.g. the sieve of Eratosthenes to find all the primes up to <math>x^{1/2}</math>).

In fact, it suffices to compute the sum

:<math>\sum_{n} c(n) \frac{\Lambda(n)}{\log n}</math> (1)

where c is a computable function which equals 1 for <math>n < x - x^{1/2}</math>, vanishes for <math>n>x</math>, and is smooth in between.  This is because the error can be computed in <math>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>x^{1/4+o(1)}</math>.]

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

:<math> \frac{1}{2\pi i} \int_{2-i\infty}^{2+i\infty} F(s) \log \zeta(s)\ ds</math>

where

:<math> 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>Im(s) \gg x^{1/2}</math>, so to get within accuracy 1/2, one only needs to evaluate the integral for <math>s = O(x^{1/2+o(1)})</math>.  By quadrature, this reduces to evaluating <math>\zeta(s)</math> (and its first few derivatives) to accuracy about <math>O(x^{-1/2+o(1)})</math> for about <math>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).