Consider numbers of the form N = k * 2^n + 1, where k is odd and n > 0. If, for some fixed k, every integer n yields a composite (non-prime) number N, then k is said to be a Sierpinski number.
The Sierpinski Problem, simply put, is: What is the smallest Sierpinski number?
John Selfridge proved in 1962 that k = 78557 is a Sierpinski number. The proof shows that every choice of n falls into at least one of seven categories, where each category guarantees a factor of N. A detailed explanation of the proof is available on TeamPrimeRib's web site.
Most mathematicians believe that 78557 is, indeed, the smallest Sierpinski number. But to prove it, we have to show that every number k < 78557 is not a Sierpinski number. Remember, a Sierpinski number is a fixed k such that all n yield composite N. So a non-Sierpinski number is a fixed k such that some choice of n yields a prime N. This turns out to be relatively easy to do for most choices of k. However, sometimes n has to grow very large before a prime number appears.
By early 2002, primes had been found for all but seventeen choices of k. At that point, the SeventeenOrBust project began a systematic DistributedComputing search of the remaining k values. Eleven of them have now been eliminated by the project, and six remain to prove that 78557 is the smallest Sierpinski number. The community is divided on the question of whether or not it is likely the SeventeenOrBust project will complete its search within its authors' lifetimes. Heuristics have been used to estimate the range of numbers that must be tested before eliminating all the remaining multipliers is likely, but most of these heuristics have been demonstrated to be inaccurate. In any case, it is very likely that SeventeenOrBust will be able to eliminate at least some of the remaining six.
The remaining k candidates are 10223, 21181, 22699, 24737, 55459 and 67607.