Finding Primes: A Fun Subproblem

The ongoing open mathematics project finding primes aims to find a deterministic algorithm to efficiently generate -digit primes. The fastest known algorithm seems to be a method of Odlyzko which generates a -digit prime in time . 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 denote the number of primes less than or equal to . 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 in time about .

Suppose you can find two -digit numbers and such that the parity of and are different. Set , i.e., take to be the midpoint between and . Compute the parity of . It must have either a different parity to or a different parity to . Repeating this procedure times, we can use a binary search to find adjacent -digit numbers and such that and have different parity. We conclude that must be prime. That takes time , and so breaks the barrier set by Odlyzko’s method.

What’s the problem with this algorithm? The problem is finding the initial -digit numbers and such that and 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?