Riesel number

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

In mathematics, a Riesel number is an odd natural number k for which the integers of the form k·2n − 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·2n − 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×2n − 1 has covering set {3, 5, 7, 13, 17, 241}
  • 762701×2n − 1 has covering set {3, 5, 7, 13, 17, 241}
  • 777149×2n − 1 has covering set {3, 5, 7, 13, 19, 37, 73}
  • 790841×2n − 1 has covering set {3, 5, 7, 13, 19, 37, 73}
  • 992077×2n − 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 OEIS A050412 (not allow that n = 0), for odd ks, see OEIS A046069 or OEIS 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 |2n - 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, |2n - 509203| is composite for all natural number n and 509203 is conjectured to be the smallest dual Riesel number.

The smallest n which 2n - k is prime are (for odd ks, and this sequence requires that 2n > 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 2n < k, the first unknown n is for k = 2293 instead of k = 1871, since 1871 - 22 = 1867 is prime.

The odd ks which k - 2n are all composite for all 2n < 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 2n > 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 in base b is a natural number k such that gcd(k − 1, b − 1) = 1 and k×bn − 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×27181987−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×3496050−1
4 9 9×4n − 1 = (3×2n − 1) × (3×2n + 1) none (proven) 8×41−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, ... 100186×52079747-1
6 84687 {7, 13, 31, 37, 97} 1597, 9582, 57492 36772×61723287−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×7298243−1
8 14 {3, 5, 13} none (proven) 11×818−1
9 4 4×9n − 1 = (2×3n − 1) × (2×3n + 1) none (proven) 2×91−1
10 10176 {7, 11, 13, 37} 4421 7019×10881309−1
11 862 {3, 7, 19, 37} none (proven) 62×1126202−1
12 25 {13} for odd n, 25×12n − 1 = (5×12n/2 − 1) × (5×12n/2 + 1) for even n none (proven) 24×124−1
13 302 {5, 7, 17} none (proven) 288×13109217−1
14 4 {3, 5} none (proven) 2×144−1
15 36370321851498 {13, 17, 113, 211, 241, 1489, 3877} 135202, 298342, 300870, 381714, 937474, 940130, 1877488, ... 2744492×1590957−1
16 9 9×16n − 1 = (3×4n − 1) × (3×4n + 1) none (proven) 8×161−1
17 86 {3, 5, 29} none (proven) 44×176488−1
18 246 {5, 13, 19} none (proven) 151×18418−1
19 144 {5} for odd n, 144×19n − 1 = (12×19n/2 − 1) × (12×19n/2 + 1) for even n none (proven) 134×19202−1
20 8 {3, 7} none (proven) 2×2010−1
21 560 {11, 13, 17} none (proven) 64×212867−1
22 4461 {5, 23, 97} 3656 3104×22161188−1
23 476 {3, 5, 53} 404 194×23211140−1
24 4 {5} for odd n, 4×24n − 1 = (2×24n/2 − 1) × (2×24n/2 + 1) for even n none (proven) 3×241−1
25 36 36×25n − 1 = (6×5n − 1) × (6×5n + 1) none (proven) 32×254−1
26 149 {3, 7, 31, 37} none (proven) 115×26520277−1
27 8 8×27n − 1 = (2×3n − 1) × (4×9n + 2×3n + 1) none (proven) 6×272−1
28 144 {29} for odd n, 144×28n − 1 = (12×28n/2 − 1) × (12×28n/2 + 1) for even n none (proven) 107×2874−1
29 4 {3, 5} none (proven) 2×29136−1
30 1369 {7, 13, 19} for odd n, 1369×30n − 1 = (37×30n/2 − 1) × (37×30n/2 + 1) for even n 659, 1024 239×30337990−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

References

  1. ↑ Lua error in package.lua at line 80: module 'strict' not found.
  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

  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.

External links

Retrieved from "https://infogalactic.com/w/index.php?title=Riesel_number&oldid=283487"