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?
Comments are closed.