Riesel number

In mathematics, a Riesel number is an odd natural number k for which the integers of the form k·2ⁿ − 1 are composite for all natural numbers n (sequence A101036 in OEIS).

In other words, when k is a Riesel number, all members of the following set are composite:

$\left\{\,k 2^n - 1 : n \in\mathbb{N}\,\right\}.$

In 1956, Hans Riesel showed that there are an infinite number of integers k such that k·2ⁿ − 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.^[1]

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×2ⁿ − 1 has covering set {3, 5, 7, 13, 17, 241}
• 762701×2ⁿ − 1 has covering set {3, 5, 7, 13, 17, 241}
• 777149×2ⁿ − 1 has covering set {3, 5, 7, 13, 19, 37, 73}
• 790841×2ⁿ − 1 has covering set {3, 5, 7, 13, 19, 37, 73}
• 992077×2ⁿ − 1 has covering set {3, 5, 7, 13, 17, 241}.

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 that 509203 is the smallest Riesel number. However, 50 values of k less than this have yielded only composite numbers for all values of n so far tested, they are

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

Thirty-three numbers have had primes found by the Riesel Sieve project (analogous to Seventeen or Bust for Sierpinski numbers). Currently, PrimeGrid is working on the remaining numbers and has found 14 primes as of 17 December 2014.^[2]

The smallest n for which $k*2^n-1$ is prime

2, 1, 0, 0, 2, 0, 1, 0, 1, 1, 2, 0, 3, 0, 1, 1, 2, 0, 1, 0, 1, 1, 4, 0, 3, 2, 1, 3, 4, 0, 1, 0, 2, 1, 2, 1, 1, 0, 3, 1, 2, 0, 7, 0, 1, 3, 4, 0, 1, 2, 1, 1, 2, 0, 1, 2, 1, 3, 12, 0, 3, 0, 2, 1, 4, 1, 5, 0, 1, 1, 2, 0, 7, 0, 1, ... (sequence A040081 in OEIS) or  A050412 (not allow that n = 0), for odd ks, see  A046069 or  A108129 (not allow that n = 0)

The first unknown n is for that k = 2293.

Simultaneously Riesel and Sierpiński

A number may be simultaneously Riesel and Sierpiński. These are called Brier numbers. The smallest five known example are 3316923598096294713661, 10439679896374780276373, 11615103277955704975673, 12607110588854501953787, 17855036657007596110949, ... (A076335).^[3]

The dual Riesel problem

The dual Riesel numbers are defined as an odd natural number k such that |2ⁿ - k| is composite for all natural number n, there is a conjecture that the set of this numbers is the same as the set of Riesel numbers, for example, |2ⁿ - 509203| is composite for all natural number n and 509203 is conjectured to be the smallest dual Riesel number.

The smallest n which 2ⁿ - k is prime are (for odd ks, and this sequence requires that 2ⁿ > k)

2, 3, 3, 39, 4, 4, 4, 5, 6, 5, 5, 6, 5, 5, 5, 7, 6, 6, 11, 7, 6, 29, 6, 6, 7, 6, 6, 7, 6, 6, 6, 8, 8, 7, 7, 10, 9, 7, 8, 9, 7, 8, 7, 7, 8, 7, 8, 10, 7, 7, 26, 9, 7, 8, 7, 7, 10, 7, 7, 8, 7, 7, 7, 47, 8, 14, 9, 11, 10, 9, 10, 8, 9, 8, 8, ... (sequence A096502 in OEIS)

The first unknown term for this sequence is that k = 1871, but if we allow that 2ⁿ < k, the first unknown n is for k = 2293 instead of k = 1871, since 1871 - 2² = 1867 is prime.

The odd ks which k - 2ⁿ are all composite for all 2ⁿ < k (the de Polignac numbers) are

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, ... (sequence A006285 in OEIS)

The unknown values of ks are (for that 2ⁿ > k)

1871, 2293, 25229, 31511, 36971, 47107, 48959, 50171, 56351, 63431, 69427, 75989, 81253, 83381, 84491, ... (sequence A216189 in OEIS)

Riesel number base b

A "Riesel number base b" is a natural number k such that gcd(k − 1, b − 1) = 1 and k×bⁿ − 1 is composite for all natural number n > 0.^[4][5]

b	Conjectured smallest Riesel k	cover set / algebraic factors	remaining k with no known primes	Largest prime found
2	509203	{3, 5, 7, 13, 17, 241}	2293, 4586, 9172, 9221, 18344, 18442, 23669, 31859, 36688, 36884, 38473, 46663, 47338, 67117, 63718, 73376, 73768, 74699, 76946, 81041, 93326, 93839, 94676, 97139, ...	502573×2^7181987−1
3	63064644938	{5, 7, 13, 17, 19, 37, 41, 193, 757}	3677878, 6793112, 6878756, 10463066, 10691528, 10789522, 11033634, 16874152, 18137648, 20379336, 20636268, 21368582, 24541466, 26093926, 29140796, ...	958234546×3^496050−1
4	9	9×4^n − 1 = (3×2^n − 1) × (3×2^n + 1)	none (proven)	8×4^1−1
5	346802	{3, 7, 13, 31, 601}	3622, 4906, 18110, 23906, 24530, 26222, 35248, 35816, 52922, 53546, 63838, 64598, 66916, 68132, 71146, 76354, 81134, 88444, 90220, 92936, ...	296024×5^2185270−1
6	84687	{7, 13, 31, 37, 97}	1597, 9582, 57492	36772×6^1723287−1
7	408034255082	{5, 13, 19, 43, 73, 181, 193, 1201}	315768, 1356018, 1620198, 2096676, 2210376, 2494112, 2539898, 2631672, 3423408, 3531018, 3587876, 3885264, 4322834, 4326672, 4363418, 4382984, 4635222, 4780002, 4870566, 4990788, ...	328226×7^298243−1
8	14	{3, 5, 13}	none (proven)	11×8^18−1
9	4	4×9^n − 1 = (2×3^n − 1) × (2×3^n + 1)	none (proven)	2×9^1−1
10	10176	{7, 11, 13, 37}	4421	7019×10^881309−1
11	862	{3, 7, 19, 37}	none (proven)	62×11^26202−1
12	25	{13} for odd n, 25×12^n − 1 = (5×12^n/2 − 1) × (5×12^n/2 + 1) for even n	none (proven)	24×12^4−1
13	302	{5, 7, 17}	none (proven)	288×13^109217−1
14	4	{3, 5}	none (proven)	2×14^4−1
15	36370321851498	{13, 17, 113, 211, 241, 1489, 3877}	135202, 298342, 300870, 381714, 937474, 940130, 1877488, 2028030, 3347624, 3889018, 4242104, 4475130, 4502952, 4513050, 4820256, ...	2744492×15^90957−1
16	9	9×16^n − 1 = (3×4^n − 1) × (3×4^n + 1)	none (proven)	8×16^1−1
17	86	{3, 5, 29}	none (proven)	44×17^6488−1
18	246	{5, 13, 19}	none (proven)	151×18^418−1
19	144	{5} for odd n, 144×19^n − 1 = (12×19^n/2 − 1) × (12×19^n/2 + 1) for even n	none (proven)	134×19^202−1
20	8	{3, 7}	none (proven)	2×20^10−1
21	560	{11, 13, 17}	none (proven)	64×21^2867−1
22	4461	{5, 23, 97}	3656	3104×22^161188−1
23	476	{3, 5, 53}	404	194×23^211140−1
24	4	{5} for odd n, 4×24^n − 1 = (2×24^n/2 − 1) × (2×24^n/2 + 1) for even n	none (proven)	3×24^1−1
25	36	36×25^n − 1 = (6×5^n − 1) × (6×5^n + 1)	none (proven)	32×25^4−1
26	149	{3, 7, 31, 37}	none (proven)	115×26^520277−1
27	8	8×27^n − 1 = (2×3^n − 1) × (4×9^n + 2×3^n + 1)	none (proven)	6×27^2−1
28	144	{29} for odd n, 144×28^n − 1 = (12×28^n/2 − 1) × (12×28^n/2 + 1) for even n	none (proven)	107×28^74−1
29	4	{3, 5}	none (proven)	2×29^136−1
30	1369	{7, 13, 19} for odd n, 1369×30^n − 1 = (37×30^n/2 − 1) × (37×30^n/2 + 1) for even n	659, 1024	239×30^337990−1

Conjectured smallest Riesel number in base n are

509203, 63064644938, 9, 346802, 84687, 408034255082, 14, 4, 10176, 862, 25, 302, 4, 36370321851498, 9, 86, 246, 144, 8, 560, 4461, 476, 4, 36, 149, 8, 144, 4, 1369, 134718, 10, 16, 6, 287860, 4, 7772, 13, 4, 81, 8, 15137, 672, 4, 22564, 8177, 14, 3226, 36, 16, ...

See also

• Sierpiński number
• Woodall number
• Experimental mathematics
• BOINC
• PrimeGrid

References

1. Riesel, Hans (1956). "Några stora primtal". Elementa 39: 258–260.
2. 14th Riesel prime discovery announcement on PrimeGrid
3. Problem 29.- Brier Numbers
4. Riesel conjectures in bases up to 1030
5. Riesel conjectures in bases which are power of 2 up to 1024

Sources

• Guy, Richard K. (2004). Unsolved Problems in Number Theory. Berlin: Springer-Verlag. p. 120. ISBN 0-387-20860-7.
• Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York: Springer-Verlag. pp. 357–358. ISBN 0-387-94457-5.

External links

• PrimeGrid
• The Riesel Problem: Definition and Status
• The Prime Glossary: Riesel number
• List of primes of the form: k*2^n-1, k<300