Project Five or Bust

One of my LCC colleagues, Phil Moore had great news in February.  I'm finally getting around to blogging about it.

He organized a search named "Five or Bust" on a math forum to organize a "proof" by overpowering evidence for the conjecture that

k = 78557 is the smallest positive odd integer such that k + 2ⁿ is never a prime number for any positive integer n

Phil writes about his project's completion:

It is easy to show that 78557 + 2^n is never prime, being always divisible by 3, 5, 7, 13, 19, 37, or 73.

To show that 78557 is the smallest number with this property, we need to find for each odd k < 78557 some value of n which makes k + 2^n prime.

A collaborative search in 2001-2002 narrowed the search down to 8 values of k for which a prime or probable prime value was not known for the sequence k + 2^n. A probable prime is a number which passes a number of tests that all prime numbers will pass and most, but not all, composite numbers will fail. I started searching these 8 sequences in summer of 2007 and eliminated three of them by discovering three large probable primes. My largest discovery in June of 2008 at 358,640 digits was at that time the largest known probable prime.

In October of 2008, I organized the distributed search project "Five or Bust" to search the remaining 5 sequences. In November 2009, we found the fourth probable prime, narrowing the search to the single sequence 40291 + 2^n.

In early February, Engracio Esmenda of Chicago discovered that 40291 + 2^9092394 is a probable prime. This number contains 2,737,083 digits, and if written in 12-point font on a single line, would be over five-and-a-half miles long. We are pretty sure that we have found our prime, but we can't actually prove it. The probability that a random number of this size which has passed all of our probable prime tests is actually composite is about 1 chance in 10^1800. To prove it is actually prime would take about 4 trillion years on a typical computer of today, maybe only 300 billion years if the Generalized Riemann Hypothesis is ever proven.

Twenty of the values that have been discovered over the years of this search are probable primes as opposed to proven primes, so in order to make a mathematical theorem out of this, we are going to need some improvements in theory, technology, or both!

This project has been so much fun that I am a little sorry to see it end, but I am also relieved, as there was no reason to think that in the worst case, the search could easily have gone on for decades.

Congratulations, Phil and Engracio!