Riesel and Sierpinski Numbers

In mathematics, a Riesel number is an odd natural number \(k\) for which \(k \times 2^n-1 \) is composite for all natural numbers \(n\). This is sequence A101036 in the OEIS. I have encountered numbers of this form before but in a different context. In a post of June 27th 2016, I wrote about Proth-like numbers that are also of the form \(k \times 2^n-1 \) and that are prime for certain values of \(k\) and \(n\). Some of these prime-producing combinations of \(k\) and \(n\) are listed on this website: 

http://www.prothsearch.com/riesel2.html

Figure 1 shows a screenshot from the opening page.

Figure 1

For example, if \(k=121\), then the initial values of \(n\) that produce primes are as follows:

1, 3, 21, 27, 37, 43, 91, 117, 141, 163, 373, 421, 1581, 2035, 10701, 18931, 21307, 51195, 64579, 156541, 302097, 334257, 368059, 383061, 410131, 494317, 541621, 990219, ...

The reason that I referred to these sorts of numbers as Proth-like is that the actual Proth numbers are of the form \(k \times 2^n+1 \) and the primes that are produced by suitable combinations of \(k\) and \(n\) are referred to as Proth primes.

Hans Ivar Riesel: biography

Riesel numbers are clearly the opposite because we are only interested in values of \(k\) that always produce composite numbers, no matter what the value of \(n\). It should be noted that a Riesel number does not refer to the prime itself but to the coefficient of \(2^n\). The currently known Riesel numbers are shown below and constitute OEIS A101036:

509203, 762701, 777149, 790841, 992077, 1106681, 1247173, 1254341, 1330207, 1330319, 1715053, 1730653, 1730681, 1744117, 1830187, 1976473, 2136283, 2251349, 2313487, 2344211, 2554843, 2924861, ...

To quote from Wikipedia:

In 1956, Hans Riesel showed that there are an infinite number of integers \(k\) such that \(k\times 2^n-1 \) is not prime for any integer \(n\). He showed that the number 509203 has this property, as does 509203 plus any positive integer multiple of 11184810. The Riesel problem consists in determining the smallest Riesel number. Because no covering set has been found for any \(k\) less than 509203, it is conjectured to be the smallest Riesel number.

To check if there are \(k < 509203\), the Riesel Sieve project (analogous to Seventeen or Bust for Sierpinski numbers) started with 101 candidate \(k\). As of January 2021, 53 of these \(k\) had been eliminated by Riesel Sieve, PrimeGrid, or outside persons. The remaining 48 values of \(k\) that have yielded only composite numbers for all values of \(n\) so far tested are

2293, 9221, 23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 161669, 192971, 206039, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743

The most recent elimination was in November 2020, when \(146561 × 2^{11280802} − 1 \) was found to be prime by PrimeGrid. This number is 3,395,865 digits long. As of January 2021, PrimeGrid has searched the remaining candidates up to \(n = 11,300,000\). 

There is also the notion of the covering set in relation to Riesel numbers. To quote again from Wikipedia:

A number can be shown to be a Riesel number by exhibiting a covering set: a set of prime numbers that will divide any member of the sequence, so called because it is said to "cover" that sequence. The only proven Riesel numbers below one million have covering sets as follows:

• \(509203\times 2^n-1\) has covering set {3, 5, 7, 13, 17, 241}
• \(762701\times 2^n-1\) has covering set {3, 5, 7, 13, 17, 241}
• \(777149\times 2^n-1\) has covering set {3, 5, 7, 13, 19, 37, 73}
• \(790841\times 2^n-1\) has covering set {3, 5, 7, 13, 19, 37, 73}
• \(992077\times 2^n-1\) has covering set {3, 5, 7, 13, 17, 241}

The concept of Riesel numbers can be extended to bases other than 10 but I won't go into that here. Instead let's consider what constitutes a Sierpinski number. Wikipedia provides this definition:

In number theory, a Sierpiński number is an odd natural number \(k\) such that \( k \times 2^n+1\) is composite for all natural numbers \(n\). In 1960, Wacław Sierpiński proved that there are infinitely many odd integers \(k\) which have this property.

Wacław Sierpiński: biography

The article continues by saying that:

The sequence of currently known Sierpiński numbers constitutes OEIS A076336 begins with:

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, 1259779, 1290677, 1518781, 1624097, 1639459, 1777613, 2131043, 2131099, 2191531, 2510177, 2541601, 2576089, 2931767, 2931991, ... 

The number 78557 was proved to be a Sierpiński number by John Selfridge in 1962, who showed that all numbers of the form \(78557 \times 2^n + 1\) have a factor in the covering set {3, 5, 7, 13, 19, 37, 73}. For another known Sierpiński number, 271129, the covering set is {3, 5, 7, 13, 17, 241}. Most currently known Sierpiński numbers possess similar covering sets. 

A number may be simultaneously Sierpiński and Riesel. These are called Brier numbers and constitute OEIS A076335. The smallest five known examples are: 

• 3316923598096294713661
• 10439679896374780276373
• 11615103277955704975673
• 12607110588854501953787
• 17855036657007596110949

There's a lot more that could be said but I'll leave it there as the essential ideas have been covered.