Odlyzko's method

From Polymath1Wiki

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

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

In fact, it suffices to compute the sum

(1)

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

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

where

.

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