Sierpinski’s problem

In early December 2016, various media, including issue 515 of the Boletín de la RSME, informed us of the discovery of a 9-million-digit prime (see also: Quo).

To some of us more interested in computational number theory records than in Olympic swimming records (and swimming trunks without polyurethane, of course), the fact that the discovery of a 9-million-digit prime was news seemed odd, given that larger primes have been known for the last 10 years. As I write this, the largest known prime is \(2^{74\,207\,201}-1\) (a Mersenne prime), which was discovered in January 2016 by Curtis Cooper within the Internet Mersenne Prime Search (GIMPS), and has \(22\,338\,618\) digits.

So what was the interest of the 9-million-digit prime to be talked about in the mainstream media? Explaining it requires more than just size, and that is what we are going to do here.

The primes of the form \(2^{2^n}+1\) are called Fermat primes (only five are known, those corresponding to \(n=0,1,2,3,4\)), and those of the form \(2^p-1\) Mersenne primes (at the moment \(49\) is known, and often the largest known prime is one of this type). There are specialised tests for testing the primality or not of such types of numbers: the Pépin test and the Lucas-Lehmer test, respectively. Less well known are the so-called Proth primes, which are those of the form \(k \cdot 2^n+1\) (with \(k<2^n\)), whose primality can be analysed with the so-called Proth test, which is similar to the Pepin and Lucas-Lehmer tests. The existence of these specialised tests (details of which can be found, for example, in my book on number theory [2]) makes it possible to find primes of these types of much larger size than the “ordinary” primes for which there are no specific tests.

By the way, a clarification: although “large” primes are very useful in cryptography, the primes required there are in the hundreds of digits; these million-digit primes currently have no cryptographic application. But even so, keeping track of progress in primality and – especially – integer factorisation algorithms is important for those involved in cybersecurity (a dramatic and unexpected breakthrough in factorisation algorithms could cause a major disaster in this field). And it can always be said that the computational work required (often months of computation on a home computer) to check the primeness of such numbers is very useful for checking the power and reliability of computers.

But let’s drop that and go back to Proth’s numbers. Actually, to Sierpinski numbers, to which they are closely related. A Sierpinski number is an odd positive integer \(k\) such that all the numbers of the set
$$
\{k \cdot 2^n+1 : n \in \mathbb{N}\}
$$
are composites (see [1] or note 3.23, page 208 of [2]). Its name alludes to the Polish mathematician Waclaw Sierpinski (1882-1969), who in 1960 proved that there exist infinite \(k\) with such a property. Not many Sierpinski numbers are known; as of this writing, the smallest ones that have been found are
$$
78\,557,\ 271\,129,\ 271\,577,\ 322\,523,\ 327\,739.
$$
It was John Selfridge (1927-2010) who in 1962 proved that \(78\,557\) is a Sierpinski number; he managed to show that, when \(k = 78\,557\), all numbers of the form \(k \cdot 2^n+1\) have a divisor in the set \(\{3, 5, 7, 13, 19, 37, 73\}\).

Determining the smallest Sierpinski number is an open problem, the so-called Sierpinski problem. In 1967, Sierpinski and Selfridge conjectured that \(k = 78\,557\) was the smallest Sierpinski number, which would solve the problem. To prove this, we must check that all odd \(k\) less than \(78,557\) are not Sierpinski numbers; that is, for each of them there exists a \(n\) such that \(k \cdot 2^n + 1\) is prime. In 2002, an intensive search was started (collaboratively via the internet) to rule out all such \(k < 78\,557\); at that point there were seventeen candidates left to eliminate, and the project was called Seventeen or Bust.

Within a short time, many candidates were discarded, and by 2007 they had been narrowed down to these six:

$$
10\,223,\ 21\,181,\ 22\,699,\ 24\,737,\ 55\,459,\ 67\,607.
$$
It seemed that Sierpinski’s problem could be solved in not too long but, since then, and despite the fact that the collaborative internet search not only continued but intensified (it was integrated into another larger distributed prime search project called PrimeGrid, with thousands of users from all over the world), there had been no progress. Until, on 31 October 2016, Hungarian Szabolcs Péter, one of the participants in the PrimeGrid project, demonstrated that
$$
10\,223 \cdot 2^{31\,172\,165}+1
$$
is a prime number (with \(9\,383\,761\) digits, seventh in the current prime number size rankings, and the largest known non-Mersenne prime). After verification by other PrimeGrid participants, the official announcement of the discovery took place a month later. This discovery eliminates the possibility that \(k=10\,223\) is a Sierpinski number, and only five more have to be ruled out for Sierpinski and Selfridge’s conjecture to become a theorem.

References

[1] W. Sierpinski,
Sur un probléme concernment les nombres $k \cdot 2^n +1$,
Elem. Math. 15, 63-74, 1960.

[2]  J. L. Varona,
Recorridos por la Teoría de Números,
Electolibris y Real Sociedad Matemática Española,
Colección Textos Universitarios, núm. 4,
Murcia, 2014.