Riesel number

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 (sequence A101036 in the OEIS). In other words, when k is a Riesel number, all members of the following set are composite:

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

If the form is instead $k\times 2^{n}+1$ , then k is a Sierpinski number.

Riesel Problem

Unsolved problem in mathematics:

Is 509,203 the smallest Riesel number?

(more unsolved problems in mathematics)

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.[1] 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.[2] 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.[3]

As of January 2021, PrimeGrid has searched the remaining candidates up to n = 11,300,000.[4]

Known Riesel numbers

The sequence of currently known Riesel numbers begins with:

509203, 762701, 777149, 790841, 992077, 1106681, 1247173, 1254341, 1330207, 1330319, 1715053, 1730653, 1730681, 1744117, 1830187, 1976473, 2136283, 2251349, 2313487, 2344211, 2554843, 2924861, ... (sequence A101036 in the OEIS)

Covering set

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 smallest n for which k · 2ⁿ − 1 is prime

Here is a sequence $a(k)$ for k = 1, 2, .... It is defined as follows: $a(k)$ is the smallest n ≥ 0 such that $k\cdot 2^{n}-1$ is prime, or -1 if no such prime exists.

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 the OEIS). The first unknown n is for that k = 2293.

Related sequences are OEIS: A050412 (not allowing n = 0), for odd ks, see OEIS: A046069 or OEIS: A108129 (not allowing n = 0)

Simultaneously Riesel and Sierpiński

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

The dual Riesel problem

The dual Riesel numbers are defined as the odd natural numbers k such that |2ⁿ - k| is composite for all natural numbers 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 numbers 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 the OEIS)

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 the OEIS)

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

1871, 2293, 25229, 31511, 36971, 47107, 48959, 50171, 56351, 63431, 69427, 75989, 81253, 83381, 84491, ...

Riesel number base b

One can generalize the Riesel problem to an integer base b ≥ 2. A Riesel number base b is a positive integer k such that gcd(k − 1, b − 1) = 1. (if gcd(k − 1, b − 1) > 1, then gcd(k − 1, b − 1) is a trivial factor of k×bⁿ − 1 (Definition of trivial factors for the conjectures: Each and every n-value has the same factor))[6][7] For every integer b ≥ 2, there are infinitely many Riesel numbers base b.

Example 1: All numbers congruent to 84687 mod 10124569 and not congruent to 1 mod 5 are Riesel numbers base 6, because of the covering set {7, 13, 31, 37, 97}. Besides, these k are not trivial since gcd(k + 1, 6 − 1) = 1 for these k. (The Riesel base 6 conjecture is not proven, it has 3 remaining k, namely 1597, 9582 and 57492)

Example 2: 6 is a Riesel number to all bases b congruent to 34 mod 35, because if b is congruent to 34 mod 35, then 6×bⁿ − 1 is divisible by 5 for all even n and divisible by 7 for all odd n. Besides, 6 is not a trivial k in these bases b since gcd(6 − 1, b − 1) = 1 for these bases b.

Example 3: All squares k congruent to 12 mod 13 and not congruent to 1 mod 11 are Riesel numbers base 12, since for all such k, k×12ⁿ − 1 has algebraic factors for all even n and divisible by 13 for all odd n. Besides, these k are not trivial since gcd(k + 1, 12 − 1) = 1 for these k. (The Riesel base 12 conjecture is proven)

Example 4: If k is between a multiple of 5 and a multiple of 11, then k×109ⁿ − 1 is divisible by either 5 or 11 for all positive integers n. The first few such k are 21, 34, 76, 89, 131, 144, ... However, all these k < 144 are also trivial k (i. e. gcd(k − 1, 109 − 1) is not 1). Thus, the smallest Riesel number base 109 is 144. (The Riesel base 109 conjecture is not proven, it has one remaining k, namely 84)

Example 5: If k is square, then k×49ⁿ − 1 has algebraic factors for all positive integers n. The first few positive squares are 1, 4, 9, 16, 25, 36, ... However, all these k < 36 are also trivial k (i. e. gcd(k − 1, 49 − 1) is not 1). Thus, the smallest Riesel number base 49 is 36. (The Riesel base 49 conjecture is proven)

We want to find and proof the smallest Riesel number base b for every integer b ≥ 2. It is a conjecture that if k is a Riesel number base b, then at least one of the three conditions holds:

All numbers of the form k×bⁿ − 1 have a factor in some covering set. (For example, b = 22, k = 4461, then all numbers of the form k×bⁿ − 1 have a factor in the covering set: {5, 23, 97})
k×bⁿ − 1 has algebraic factors. (For example, b = 9, k = 4, then k×bⁿ − 1 can be factored to (2×3ⁿ − 1) × (2×3ⁿ + 1))
For some n, numbers of the form k×bⁿ − 1 have a factor in some covering set; and for all other n, k×bⁿ − 1 has algebraic factors. (For example, b = 19, k = 144, then if n is odd, then k×bⁿ − 1 is divisible by 5, if n is even, then k×bⁿ − 1 can be factored to (12×19^n/2 − 1) × (12×19^n/2 + 1))

In the following list, we only consider those positive integers k such that gcd(k − 1, b − 1) = 1, and all integer n must be ≥ 1.

Note: k-values that are a multiple of b and where k−1 is not prime are included in the conjectures (and included in the remaining k with red color if no primes are known for these k-values) but excluded from testing (Thus, never be the k of "largest 5 primes found"), since such k-values will have the same prime as k / b.

b	conjectured smallest Riesel k	covering set / algebraic factors	remaining k with no known primes (red indicates the k-values that are a multiple of b and k−1 is not prime)	number of remaining k with no known primes (excluding the red ks)	testing limit of n (excluding the red ks)	largest 5 primes found (excluding red ks)
2	509203	{3, 5, 7, 13, 17, 241}	2293, 4586, 9172, 9221, 18344, 18442, 23669, 31859, 36688, 36884, 38473, 46663, 47338, 63718, 67117, 73376, 73768, 74699, 76946, 81041, 93326, 93839, 94676, 97139, 107347, 121889, 127436, 129007, 134234, 143047, 146561, 146752, 147536, 149398, 153892, 161669, 162082, 186652, 187678, 189352, 192971, 194278, 206039, 206231, 214694, 215443, 226153, 234343, 243778, 245561, 250027, 254872, 258014, 268468, 286094, 293122, 293504, 295072, 298796, 307784, 315929, 319511, 323338, 324011, 324164, 325123, 327671, 336839, 342847, 344759, 351134, 362609, 363343, 364903, 365159, 368411, 371893, 373304, 375356, 378704, 384539, 385942, 386801, 388556, 397027, 409753, 412078, 412462, 429388, 430886, 444637, 452306, 468686, 470173, 474491, 477583, 478214, 485557, 487556, 491122, 494743, 500054	49	k = 351134 and 478214 at n = 4.7M, k = 342847 and 444637 at n = 10M. PrimeGrid is currently searching all other ks at n > 8.9M	273809×2^8932416-1[8] 502573×2^7181987−1 402539×2^7173024−1 40597×2^6808509−1 304207×2^6643565−1
3	63064644938	{5, 7, 13, 17, 19, 37, 41, 193, 757}	3677878, 6793112, 10463066, 10789522, 11033634, 16874152, 18137648, 20379336, 21368582, 29140796, 31064666, 31389198, 32368566, 33100902, 38394682, 40175404, 40396658, 50622456, 51672206, 52072432, 54412944, 56244334, 59077924, 59254534, 61138008, 62126002, 62402206, 64105746, 65337866, 71248336, 87422388, 88126834, 93193998, 94167594, 94210372, 97105698, 97621124, 99302706, ...	150322	k = 3677878 at n = 5M, 4M < k ≤ 2.147G at n = 900K, 2.147G < k ≤ 6G at n = 500K, 6G < k ≤ 10G at n = 225K, 10G < k ≤ 25G at n = 100K, 25G < k ≤ 55G at n = 50K, 55G < k ≤ 60G at n = 100K, 60G < k ≤ 63G at n = 50K, k > 63G at n = 500K	756721382×3⁸⁹⁹⁶⁹⁸−1 1552470604×3⁸⁹⁶⁷³⁵−1 698408584×3⁸⁹¹⁸²³−1 1237115746×3⁸⁷⁹⁹⁴¹−1 10691528×3⁸⁷⁷⁵⁴⁶−1
4	9	9×4ⁿ − 1 = (3×2ⁿ − 1) × (3×2ⁿ + 1)	none (proven)	0	−	8×4¹−1 6×4¹−1 5×4¹−1 3×4¹−1 2×4¹−1
5	346802	{3, 7, 13, 31, 601}	3622, 4906, 18110, 23906, 24530, 26222, 35248, 52922, 63838, 64598, 68132, 71146, 76354, 81134, 88444, 90550, 92936, 102818, 102952, 109238, 109862, 119530, 122650, 127174, 131110, 131848, 134266, 136804, 143632, 145462, 145484, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 176240, 177742, 179080, 182398, 187916, 189766, 190334, 195872, 201778, 204394, 206894, 213988, 231674, 239062, 239342, 246238, 248546, 259072, 264610, 265702, 267298, 271162, 273662, 285598, 285728, 298442, 304004, 313126, 318278, 319190, 322498, 322990, 325922, 335414, 338866, 340660	62	PrimeGrid is currently testing at n>3M	109838×5^3168862-1[9] 207494×5^3017502-1[10] 238694×5^2979422-1[11] 146264×5^2953282-1[12] 35816×5^2945294-1[13]
6	84687	{7, 13, 31, 37, 97}	1597, 9582, 57492	1	5M	36772×6^1723287−1 43994×6⁵⁶⁹⁴⁹⁸−1 77743×6⁵⁶⁰⁷⁴⁵−1 51017×6⁵²⁸⁸⁰³−1 57023×6⁴⁸³⁵⁶¹−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, 5119538, 5333174, 5529368, 5646066, 6279074, 6463028, 6544614, 6597704, 7030248, 7115634, 7320606, 7446728, 7553594, 8057622, 8354966, 8389476, 8640204, 8733908, 8737902, 9012942, 9492126, 9761156, 9829784, 9871172, ...	8391 ks ≤ 500M	k ≤ 2M at n = 350K, 2M < k ≤ 110M at n = 150K, 110M < k ≤ 500M at n = 25K	328226×7²⁹⁸²⁴³−1 623264×7²⁴⁰⁰⁶⁰−1 1365816×7²³²⁰⁹⁴−1 839022×7¹⁹⁰⁵³⁸−1 29142942×7¹⁴⁹²⁰¹−1
8	14	{3, 5, 13}	none (proven)	0	−	11×8¹⁸−1 5×8⁴−1 12×8³−1 7×8³−1 2×8²−1
9	4	4×9ⁿ − 1 = (2×3ⁿ − 1) × (2×3ⁿ + 1)	none (proven)	0	−	2×9¹−1
10	10176	{7, 11, 13, 37}	4421	1	1.72M	7019×10⁸⁸¹³⁰⁹−1 8579×10³⁷³²⁶⁰−1 6665×10⁶⁰²⁴⁸−1 1935×10⁵¹⁸³⁶−1 1803×10⁴⁵⁸⁸²−1
11	862	{3, 7, 19, 37}	none (proven)	0	−	62×11²⁶²⁰²−1 308×11⁴⁴⁴−1 172×11¹⁸⁷−1 284×11¹⁸⁶−1 518×11⁷⁸−1
12	25	{13} for odd n, 25×12ⁿ − 1 = (5×12^n/2 − 1) × (5×12^n/2 + 1) for even n	none (proven)	0	−	24×12⁴−1 18×12²−1 17×12²−1 13×12²−1 10×12²−1
13	302	{5, 7, 17}	none (proven)	0	−	288×13¹⁰⁹²¹⁷−1 146×13³⁰−1 92×13²³−1 102×13²⁰−1 300×13¹⁰−1
14	4	{3, 5}	none (proven)	0	−	2×14⁴−1 3×14¹−1
15	36370321851498	{13, 17, 113, 211, 241, 1489, 3877}	381714, 3347624, 3889018, 4242104, 4502952, 5149158, 5237186, 5255502, 5725710, 5854146, 7256276, 8524154, 9105446, 9535278, 9756404, ...	14 ks ≤ 10M	k ≤ 10M at n = 200K	937474×15¹⁹⁵²⁰⁹−1 9997886×15¹⁸⁰³⁰²−1 8168814×15¹⁵⁸⁵⁹⁶−1 300870×15¹⁵⁶⁶⁰⁸−1 940130×15¹⁴⁷⁰⁰⁶−1
16	9	9×16ⁿ − 1 = (3×4ⁿ − 1) × (3×4ⁿ + 1)	none (proven)	0	−	8×16¹−1 5×16¹−1 3×16¹−1 2×16¹−1
17	86	{3, 5, 29}	none (proven)	0	−	44×17⁶⁴⁸⁸−1 36×17²⁴³−1 10×17¹¹⁷−1 26×17¹¹⁰−1 58×17³⁵−1
18	246	{5, 13, 19}	none (proven)	0	−	151×18⁴¹⁸−1 78×18¹⁷²−1 50×18¹¹⁰−1 79×18⁶³−1 237×18⁴⁴−1
19	144	{5} for odd n, 144×19ⁿ − 1 = (12×19^n/2 − 1) × (12×19^n/2 + 1) for even n	none (proven)	0	−	134×19²⁰²−1 104×19¹⁸−1 38×19¹¹−1 128×19¹⁰−1 108×19⁶−1
20	8	{3, 7}	none (proven)	0	−	2×20¹⁰−1 6×20²−1 5×20²−1 7×20¹−1 3×20¹−1
21	560	{11, 13, 17}	none (proven)	0	−	64×21²⁸⁶⁷−1 494×21⁹⁷⁸−1 154×21¹⁰³−1 84×21⁸⁸−1 142×21⁴⁸−1
22	4461	{5, 23, 97}	3656	1	2M	3104×22¹⁶¹¹⁸⁸−1 4001×22³⁶⁶¹⁴−1 2853×22²⁷⁹⁷⁵−1 1013×22²⁶⁰⁶⁷−1 4118×22¹²³⁴⁷−1
23	476	{3, 5, 53}	404	1	1.35M	194×23²¹¹¹⁴⁰−1 134×23²⁷⁹³²−1 394×23²⁰¹⁶⁹−1 314×23¹⁷²⁶⁸−1 464×23⁷⁵⁴⁸−1
24	4	{5} for odd n, 4×24ⁿ − 1 = (2×24^n/2 − 1) × (2×24^n/2 + 1) for even n	none (proven)	0	−	3×24¹−1 2×24¹−1
25	36	36×25ⁿ − 1 = (6×5ⁿ − 1) × (6×5ⁿ + 1)	none (proven)	0	−	32×25⁴−1 30×25²−1 26×25²−1 12×25²−1 2×25²−1
26	149	{3, 7, 31, 37}	none (proven)	0	−	115×26⁵²⁰²⁷⁷−1 32×26⁹⁸¹²−1 73×26⁵³⁷−1 80×26³⁸²−1 128×26³⁰⁰−1
27	8	8×27ⁿ − 1 = (2×3ⁿ − 1) × (4×9ⁿ + 2×3ⁿ + 1)	none (proven)	0	−	6×27²−1 4×27¹−1 2×27¹−1
28	144	{29} for odd n, 144×28ⁿ − 1 = (12×28^n/2 − 1) × (12×28^n/2 + 1) for even n	none (proven)	0	−	107×28⁷⁴−1 122×28⁷¹−1 101×28⁵³−1 14×28⁴⁷−1 90×28³⁶−1
29	4	{3, 5}	none (proven)	0	−	2×29¹³⁶−1
30	1369	{7, 13, 19} for odd n, 1369×30ⁿ − 1 = (37×30^n/2 − 1) × (37×30^n/2 + 1) for even n	659, 1024	2	500K	239×30³³⁷⁹⁹⁰−1 249×30¹⁹⁹³⁵⁵−1 225×30¹⁵⁸⁷⁵⁵−1 774×30¹⁴⁸³⁴⁴−1 25×30³⁴²⁰⁵−1
31	134718	{7, 13, 19, 37, 331}	6962, 55758	2	1M	126072×31³⁷⁴³²³−1 43902×31²⁵¹⁸⁵⁹−1 55940×31¹⁹⁷⁵⁹⁹−1 101022×31¹³³²⁰⁸−1 37328×31¹²⁹⁹⁷³−1
32	10	{3, 11}	none (proven)	0	−	3×32¹¹−1 2×32⁶−1 9×32³−1 8×32²−1 5×32²−1

Conjectured smallest Riesel number base n are (start with n = 2)

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, 64, 900, 5392, 4, 6852, 20, 144, 105788, 4, 121, 13484, 8, 187258666, 9, ... (sequence A273987 in the OEIS)

References

Riesel, Hans (1956). "Några stora primtal". Elementa. 39: 258–260.
"The Riesel Problem statistics". PrimeGrid.
Brown, Scott (25 November 2020). "TRP Mega Prime!". PrimeGrid. Retrieved 26 November 2020.
"The Riesel Problem statistics". PrimeGrid. Archived from the original on 21 January 2021. Retrieved 21 January 2021.
"Problem 29.- Brier Numbers".
"Riesel conjectures and proofs".
"Riesel conjectures & proofs powers of 2".
"TRP Mega Prime!". www.primegrid.com.
Brown, Scott (20 August 2020). "SR5 Mega Prime!". PrimeGrid. Retrieved 21 August 2020.
Brown, Scott (31 March 2020). "And Another SR5 Mega Prime!". PrimeGrid. Retrieved 1 April 2020.
Brown, Scott (31 March 2020). "Another SR5 Mega Prime!". PrimeGrid. Retrieved 1 April 2020.
Brown, Scott (31 March 2020). "SR5 Mega Prime!". PrimeGrid. Retrieved 1 April 2020.
Brown, Scott (11 March 2020). "SR5 Mega Prime!". PrimeGrid. Retrieved 11 March 2020.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Riesel, Hans (1956). "Några stora primtal". Elementa. 39: 258–260.

[2] "The Riesel Problem statistics". PrimeGrid.

[3] Brown, Scott (25 November 2020). "TRP Mega Prime!". PrimeGrid. Retrieved 26 November 2020.

[4] "The Riesel Problem statistics". PrimeGrid. Archived from the original on 21 January 2021. Retrieved 21 January 2021.

[5] "Problem 29.- Brier Numbers".

[6] "Riesel conjectures and proofs".

[7] "Riesel conjectures & proofs powers of 2".

[8] "TRP Mega Prime!". www.primegrid.com.

[9] Brown, Scott (20 August 2020). "SR5 Mega Prime!". PrimeGrid. Retrieved 21 August 2020.

[10] Brown, Scott (31 March 2020). "And Another SR5 Mega Prime!". PrimeGrid. Retrieved 1 April 2020.

[11] Brown, Scott (31 March 2020). "Another SR5 Mega Prime!". PrimeGrid. Retrieved 1 April 2020.

[12] Brown, Scott (31 March 2020). "SR5 Mega Prime!". PrimeGrid. Retrieved 1 April 2020.

[13] Brown, Scott (11 March 2020). "SR5 Mega Prime!". PrimeGrid. Retrieved 11 March 2020.