Numbers that never make a prime

Many sequences of whole numbers look as if they should contain infinitely many primes, and almost nothing can be proved about any of them. Which infinitudes are proved is a short list. Nobody knows that $n^2 + 1$ is prime infinitely often, or that there are infinitely many primes of the form $2^n + 1$, and for that one the evidence points the other way. Take the form $k \cdot 2^n + 1$ with $k$ odd. For a fixed $k$, as $n$ runs through 1, 2, 3, …, the numbers grow quickly, and a number near $2^n$ has about one chance in $n \ln 2$ of being prime. Since $\sum 1/n$ diverges, a fixed $k$ might be expected to produce infinitely many primes. For nearly every $k$ that is what seems to happen.

So it is a real surprise that Wacław Sierpiński proved in 1960 that there are infinitely many odd $k$ for which $k \cdot 2^n + 1$ is never prime, not for any $n$. Such a $k$ is called a Sierpiński number. The smallest known is 78,557, found by John Selfridge in 1962. Its proof of compositeness has nothing to do with the size of the numbers and it is short enough to draw.

Seven primes on a schedule #

Choose a prime $p$, and look at $k \cdot 2^n + 1$ modulo $p$ as $n$ grows. Since the powers of two go round a cycle modulo $p$, of length equal to the order of 2 modulo $p$, the values repeat. For $k = 78{,}557$ and $p = 3$, the order is 2, and 3 divides the number when $n$ is even. That takes care of half the exponents. For $p = 5$, the order is 4, and 5 divides it when $n \equiv 1 \pmod 4$. For $p = 7$, the order is 3, and 7 divides it when $n \equiv 1 \pmod 3$. Then 13 when $n \equiv 11 \pmod{12}$, 19 when $n \equiv 15 \pmod{18}$, 37 when $n \equiv 27 \pmod{36}$ and 73 when $n \equiv 3 \pmod 9$.

Those seven conditions, in the seven rows of the figure, cover every whole number $n$, as the bottom row shows. Every $n$ falls in at least one, and the pattern repeats every 36 steps, since 36 is the least common multiple of the orders. So for every $n$, the number $78{,}557 \cdot 2^n + 1$ has one of those seven primes as a factor, and since the number is larger than 73, it is composite. Every one of infinitely many numbers has a small known factor, identified by nothing more than its exponent modulo 36.

The largest of those seven primes is 73 and the schedule has period 36, so the whole proof is a finite check. There is a second kind of Sierpiński number too, such as $271{,}129$, with a different covering.

Six primes are enough here: 3, 5, 7, 13, 17 and 241, with period 24. Given one covering, infinitely many Sierpiński numbers follow at once. If a $k$ has a covering with primes $p_1, \dots, p_r$, then any $k'$ that is congruent to $k$ modulo all those primes and modulo 2 has the same covering, and an arithmetic progression of such numbers exists by the Chinese remainder theorem. That is exactly Sierpiński’s proof: choose primes dividing $2^{2^j} + 1$ for a set of small $j$, and build a covering from their orders. It uses the seven factors of the first few Fermat numbers, and it leads directly to a large explicit example.

Sierpiński’s own example #

The original construction shows where such coverings come from, and it uses numbers already familiar for another reason. The Fermat numbers $F_j = 2^{2^j} + 1$ are 3, 5, 17, 257, 65,537, and then $F_5 = 641 \times 6{,}700{,}417$. Every whole number $n$ has a highest power of two dividing it, $2^j$. If $j \le 4$, then $2^n \equiv -1$ modulo $F_j$. If $j = 5$ then $2^n \equiv -1$ modulo 641 as well. If $j \ge 6$, then $2^n \equiv 1$ modulo 6,700,417. So the classes by highest power of two make a covering, and every $n$ belongs to exactly one of them.

So choose $k$ by the method of several dials: $k \equiv 1$ modulo each of 3, 5, 17, 257, 65,537 and 641, and $k \equiv -1$ modulo 6,700,417. Then for each $n$, the number $k \cdot 2^n + 1$ is $-1 + 1 = 0$ modulo one of the seven primes. The smallest such odd $k$ is a number of 20 digits, about $1.55 \times 10^{19}$, and a direct test of the seven congruences at every $n$ to 4,096 confirms the covering. Compared with 78,557 it is enormous. Selfridge’s example shows how much smaller a covering can be when the primes are chosen with care: he uses periods that divide 36 and that overlap efficiently, and not the rigid scheme of powers of two.

It is a pretty coincidence that the failure of the Fermat numbers to stay prime is what makes this construction possible. Euler’s discovery that 641 divides $F_5$, which ended a famous conjecture about those numbers, gives the last two primes that the argument needs. If $F_5$ had been prime the covering would have needed more care: its single large prime would have had to handle the class $j = 5$, and with no other prime available the class $j \ge 6$ would have had nothing left to cover it. It would then have been necessary to continue through the Fermat numbers for ever.

Why most $k$ are not like this #

For almost all $k$, nothing resists. The search here tests every odd $k$ below 2,000 up to $n = 300$, using strong probable-prime tests, and most values of $k$ produce a prime immediately. Only 8 of the 1,000 values of $k$ go past $n = 300$: 47, 383, 881, 1,201, 1,643, 1,699, 1,727 and 1,741. They are not special. In the published tables, 47 gives a prime at $n = 583$, and 383 at $n = 6{,}393$, the slowest of all small cases. Among the ones that succeed within the tested range, 257 takes the longest here, at $n = 279$.

So the distribution of the first prime is very wide, and that is just what a chance model predicts. For a given $k$ the primes are thinly spread, as the next figure shows, and there are always some $k$ whose first success comes unusually late. Telling apart a $k$ that is merely late from one with a hidden obstruction is the whole difficulty.

The single sequence with $k = 3$ gives primes at the exponents 1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408 and 438. On a logarithmic scale in $n$, the staircase has a steady slope with long gaps, such as the jump from 66 to 189. That is the signature of a heuristic count $\sum c/n$, which grows like $\ln n$: a Poisson process in the variable $\ln n$. Each of the classical questions about such forms is similar in that nothing here has been proved. No specific $k$ is known to give infinitely many primes. The infinitude is in this sense a statistical prediction, of a kind that the patterns primes are allowed to make discusses for other families, where only local obstructions are allowed to stop primes appearing. Hardy and Littlewood’s conjectures and the Bateman–Horn formula have that form, and a covering is a local obstruction spread out over many primes.

Covering systems #

The mechanism is more general than this application, and Paul Erdős deserves the credit for it. A covering system is a finite list of arithmetic progressions that together contain every integer. The simplest one with distinct moduli has five members.

The classes 0 mod 2, 0 mod 3, 1 mod 4, 5 mod 6 and 7 mod 12 cover the integers. Their densities add up to $1/2 + 1/3 + 1/4 + 1/6 + 1/12 = 1.333$, so there is some overlap, which is unavoidable. It is impossible for a covering with distinct moduli to have density exactly 1, in a short proof with roots of unity that goes back to Mirsky, Newman and others. Erdős invented the idea in 1950 to settle a question of Alphonse de Polignac.

Polignac had guessed in 1849 that every odd number is the sum of a prime and a power of two. He claimed to have checked this up to three million, but 127 is already a counterexample, as subtracting 1, 2, 4, 8, 16, 32 or 64 from it leaves a composite number.

Nikolai Romanoff proved in 1934 that a positive proportion of odd numbers do have the form. The computation here gives a share of 0.929 at 200,000. The list of those that do not begins 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809. What Erdős proved is that infinitely many do not, and in fact a whole arithmetic progression does not. Build a covering with moduli equal to orders of 2 modulo various primes. Then choose an $m$ so that, for each power $2^n$, $m - 2^n$ is divisible by the prime assigned to $n$’s class. So $m - 2^n$ is composite for every $n$, and $m$ is not a prime plus a power of two. It is the same trick as Sierpiński’s a decade before him, with subtraction in place of multiplication. Ronald Graham used it in 1964 for a third purpose, to find a Fibonacci-like sequence, with coprime starting values, that contains no primes at all. Its starting values have 34 digits each, and they come from a covering by the periods of the Fibonacci numbers modulo primes.

There is also the mirror image of the Sierpiński problem, the Riesel numbers $k$ with $k \cdot 2^n - 1$ always composite, for which the smallest known is 509,203, and there are numbers called Brier numbers that are both. All of them work through coverings.

Sixty years of search #

If a covering is the only known obstruction, is it possible that no $k$ below 78,557 has one? That is Selfridge’s conjecture: 78,557 is the smallest Sierpiński number. To prove it, one must show that each smaller odd $k$ gives at least one prime. For most of them, that was easy. By the 1990s the list of those without a known prime had come down to 17.

So began a distributed project, called Seventeen or Bust, in 2002. It eliminated eleven of them in five years. The primes it found are among the largest ever known, of the special form a Proth test can decide. Then PrimeGrid continued the search, and in 2016 it found $10{,}223 \cdot 2^{31{,}172{,}165} + 1$, a number with about 9.4 million digits, the record for a non-Mersenne prime at the time. Five candidates remain: 21,181, 22,699, 24,737, 55,459 and 67,607. Each has been tested past $n = 40$ million or so, without success, and chance alone predicts that each will eventually succeed. But the chance model also predicts that it could take many times longer than all the work done so far.

The Proth test used in this search is a good example of how far a special form helps. To prove a number of this size is prime, it is enough to check a single power: $a^{(N-1)/2} \equiv -1 \pmod N$. That is the order argument in the Lucas test specialised to numbers where $N - 1$ is almost entirely a power of two, so nothing has to be factored. That is also why the primes of this form are almost the only numbers of this size for which primality can be proved at all.

What would count as a surprise #

Sequences that do have an obstruction are not always covered in this simple way. The statement that every Sierpiński number has a covering has not been proved, and it might not be true. Michael Filaseta and collaborators have studied the possibility of $k$ for which every term is composite without any covering at all. There is a strange and specific candidate: for a perfect fourth power $k = x^4$ and $n \equiv 2 \pmod 4$, the term is $4y^4 + 1$ with $y = x \cdot 2^{(n-2)/4}$, and this has an algebraic factorisation $(2y^2 + 2y + 1)(2y^2 - 2y + 1)$. So a partial covering by small primes on most residues, together with an algebraic factorisation on the rest, can also yield a sequence of only composites, and it would not be a covering in the strict sense. Izotov and others have given specific examples of this kind. Whether anything still stranger can happen is not known.

And nothing has been proved about any of the numbers that do not have a covering. For a given $k$ such as 3, the theorem that there are infinitely many primes of the form $3 \cdot 2^n + 1$ is beyond any current method. So here is a rather odd situation: the “negative” results are simple and exact, and the “positive” ones are heuristic. The sieve methods discussed in the sieve that cannot finish cannot help, because they work for sequences of positive density, and this sequence is exponentially thin. It is similar to the question in when Euclid’s number is itself prime, where the numbers also grow far too quickly for any method except looking.

What is proved, tested and quoted #

The coverings of 78,557 and 271,129 were verified exactly. Both can be checked by hand from the seven or six congruences, and they are complete proofs. The primality tests in the first-prime search are strong probable-prime tests to five bases, so strictly these are probable primes. For these sizes a false positive is extremely unlikely. The first-prime table shows only what happens up to $n = 300$, and the eight unresolved values were left unresolved here, though published results have settled them. The count for $k = 3$ agrees with the published list up to the range shown.

The statements about the resolved cases and the remaining five are quoted from the Seventeen or Bust and PrimeGrid projects. Those computations took many years of many computers, and they were not recomputed. The density heuristic is not a theorem. The share of odd numbers of the form $p + 2^n$ is an exact count, up to 200,000. Romanoff’s theorem says only that it stays above a positive constant, and the value of the limit, which has been estimated at about 0.43 or so of all integers, is not settled.

Still open: five numbers, and the covering problem #

Is 78,557 the smallest Sierpiński number? Five primes would settle it, and they could be found tomorrow or not in this century. Finding one is purely a matter of machine time, with no room left for clever mathematics, but the time needed grows much faster than any search can keep up with, since each test of a number with $n$ near 50 million takes days.

The covering systems themselves have provided the more interesting open mathematics recently. Erdős asked in 1950 whether the smallest modulus in a distinct covering can be made as large as desired. For decades constructions pushed it up, reaching 42 by 2014. In 2015 Bob Hough proved that the answer is no: every distinct covering has a least modulus below $10^{16}$. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe and Marius Tiba brought this down to 616,000 in 2018, with a new method. The companion question, whether all the moduli can be odd, posed by Erdős and Selfridge, is still open. Hough and Pace Nielsen showed that a distinct covering must use a modulus divisible by 2 or by 3, but not that it must use an even one. The schedule of the opening figure has both factors in its period, and a negative answer would say that this is no accident.

An obstruction that is a timetable #

$78{,}557 \cdot 2^n + 1$ is composite for every $n$ because seven primes divide it on a timetable of period 36 that covers every step. That is a finite proof about infinitely many numbers, and it is much the strongest statement known about any such sequence. For a typical $k$, all the evidence, from the first few hundred steps to the largest primes yet found, says primes keep appearing, and nothing has ever been proved about that. Five smaller values of $k$ remain to be resolved.

It is striking how easily a sequence can be proved to contain no primes, and how impossible it has been to show that any sequence of this kind contains infinitely many. The proof of the negative is a table that could be written on a card, and the positive statement is still out of reach of all known methods.