Skip to content

Finding Primes: A Fun Subproblem

by Michael Nielsen on September 1, 2009

The ongoing open mathematics project finding primes aims to find a deterministic algorithm to efficiently generate k-digit primes. The fastest known algorithm seems to be a method of Odlyzko which generates a k-digit prime in time O(10^{k/2}). The people working on the project have made some observations which come tantalizingly close to breaking that barrier. The obstruction is a beautiful little problem that I thought many people might enjoy, and which may well be tractable. If you’re interested in participating in the finding primes project, it might be a good entry point. So if you’ve got a good idea to solve the problem, pitch in and help over at the Polymath blog. But please be polite: read some background first, and take a look at some of the research threads to get a feel for how things work, and what’s already known.

One small caveat: the argument that follows is not in any way mine, it’s all the work of other people! A recent comment thread on this argument starts here.

Let \pi(x) denote the number of primes less than or equal to x. \pi(x) has a lot of structure, and there’s a surprising amount that can be said about it. In particular, the people working on finding primes have figured out a clever way of computing the parity of \pi(x) in time about x^{5/11+o(1)}.

Suppose you can find two k-digit numbers x and y such that the parity of \pi(x) and \pi(y) are different. Set z = \lfloor (x+y)/2 \rfloor, i.e., take z to be the midpoint between x and y. Compute the parity of z. It must have either a different parity to x or a different parity to y. Repeating this procedure O(k) times, we can use a binary search to find adjacent k-digit numbers p-1 and p such that \pi(p-1) and \pi(p) have different parity. We conclude that p must be prime. That takes time O(10^{5/11 k + o(1)}), and so breaks the barrier set by Odlyzko’s method.

What’s the problem with this algorithm? The problem is finding the initial k-digit numbers x and y such that \pi(x) and \pi(y) have different parity. It would surprise me a great deal if this weren’t possible, but it’s not obvious (at least to me) how to do it quickly. Is there a fast way of doing this?

Comments are closed.