How do you solve a problem like Sierpinski?

 That calculation took nearly 9 days on a single core of his Intel i7 'Haswell' CPU using the LLR program, and after a further 7 days our internal validation double-check was completed and the find could be officially announced. Not only was this the largest prime ever found by PrimeGrid (with 9,383,761 decimal digits, comfortably beating a 3,580,969 digit Proth prime we found last year) and the only non-Mersenne prime in the top 10 largest known primes (entering the list at number 7), it also happens to be one of the 6 remaining unknown Colbert Numbers, part of the solution to the Sierpinski Problem. To get a handle on just how massive this number is, you can download a PDF copy of it (10.6MB, 1643 pages), just please don't print it!

A little bit of maths history to help explain why this prime is important. The Sierpinski Problem is a long-standing open problem in Number Theory, postulated by John Selfridge in 1962. Waclaw Sierpinski proved in 1960 that:

There exist infinitely many odd integers k such that k · 2n + 1 is composite (i.e. not a prime) for every n ≥ 1.

Sierpinski Numbers are the integers k that have this peculiar property. Selfridge found that k=78557 was one such Sierpinski number, and the conjecture is that it is in fact the smallest of them. To prove the conjecture, the strategy is easy - just find a value of n which gives a prime for every k smaller than 78557. In practise this turns out to be a really hard computational problem! By 2002, various mathematicians had found primes for all values but 17 values of k, and a volunteer computing project was set up called "Seventeen or Bust!" to try to find the last 17 primes (the "Bust" comes from the fact that if Selfridge's conjecture is wrong, at least one of those 17 k values is a Sierpinski Number, and no prime will ever be found).  They developed a bespoke software client which participants could download and run on their home computers, testing higher and higher n values, until primes were found. By 2007, 11 of the 17 remaining k values had been eliminated, leaving 6 candidate Sierpinski numbers remaining.

In the meantime, things were changing in the world of volunteer computing. Rather than individual projects with their own software (GIMPS, SETI@Home, Distributed.net and Folding@Home being some examples), the Berkeley Open Infrastructure for Network Computing (BOINC) was gaining traction, and now has over 80 individual projects running using a single client. One of the largest projects on BOINC is PrimeGrid – I'm one of the admin team – and Seventeen or Bust started collaborating with us in 2010. This was fortuitous for several reasons, not least because earlier this year Seventeen or Bust did indeed go bust, suffering a total datacentre disaster, and with no off-site backup the project became defunct.  Work to solve the Sierpinski Problem continues now at PrimeGrid, so it was very pleasing to finally find a prime and make some progress on the problem 9 years after the previous k was eliminated.

To give you some idea how much computation is involved, since PrimeGrid joined the Seventeen or Bust search in 2010 we have completed nearly 65,000 primality tests which would have taken roughly 2500 years for a single CPU core to complete!  As well as the Sierpinski Problem, PrimeGrid also has sub-projects working on a range of related conjectures: the Prime Sierpinski Problem, Extended Sierpinski Problem and the Reisel Problem. If you want to read more about them, head to Wilfrid Keller's excellent website. Despite continued improvements in software and hardware, there is still a lot of work to be done to find primes for the 5 remaining k values. Of course, primes occur in an unpredictable manner so if you're interested, please join the project and crunch away at some of the primality tests. Who knows, you could be the next lucky finder of one of these enormous primes!