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.
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?