В математике число Ризеля — это нечетное натуральное число k , для которого является составным для всех натуральных чисел n (последовательность A101036 в OEIS ). Другими словами, когда k — число Ризеля, все члены следующего множества являются составными:
Если вместо этого используется форма , то k — число Серпинского .
В 1956 году Ганс Ризель показал, что существует бесконечное число целых чисел k, таких, что не является простым для любого целого числа n . Он показал, что число 509203 обладает этим свойством, как и 509203 плюс любое положительное целое число , кратное 11184810. [1] Задача Ризеля состоит в определении наименьшего числа Ризеля. Поскольку не было найдено покрывающего множества для любого k , меньшего 509203, предполагается , что оно является наименьшим числом Ризеля.
Чтобы проверить, есть ли k < 509203, проект Riesel Sieve (аналог Seventeen или Bust для чисел Серпинского ) начался со 101 кандидата k . По состоянию на декабрь 2022 года 57 из этих k были исключены Riesel Sieve, PrimeGrid или сторонними лицами. [2] Оставшиеся 42 значения k , которые дали только составные числа для всех значений n , проверенных до сих пор, следующие:
Последнее исключение было в апреле 2023 года, когда Райан Проппер обнаружил, что 97139 × 2 18397548 − 1 является простым числом. Это число имеет длину 5 538 219 цифр.
По состоянию на январь 2023 года PrimeGrid провел поиск оставшихся кандидатов до n = 14 900 000. [3]
Последовательность известных в настоящее время чисел Ризеля начинается с:
Число может быть показано как число Ризеля, если показать покрывающий набор : набор простых чисел, который разделит любого члена последовательности, так называемый потому, что он, как говорят, "покрывает" эту последовательность. Единственные доказанные числа Ризеля ниже миллиона имеют покрывающие наборы следующим образом:
Вот последовательность для k = 1, 2, .... Она определяется следующим образом: это наименьшее n ≥ 0, такое что является простым числом, или −1, если такого простого числа не существует.
Связанные последовательности : OEIS : A050412 (не допускает n = 0), для нечетных k см. OEIS : A046069 или OEIS : A108129 (не допускает n = 0).
Число может быть одновременно числом Ризеля и числом Серпинского . Они называются числами Бриера. Пять наименьших известных примеров: 3316923598096294713661, 10439679896374780276373, 11615103277955704975673, 12607110588854501953787, 17855036657007596110949, ... (A076335). [4]
Двойственные числа Ризеля определяются как нечетные натуральные числа k, такие, что |2 n - k | является составным для всех натуральных чисел n . Существует гипотеза, что набор этих чисел совпадает с набором чисел Ризеля. Например, |2 n - 509203| является составным для всех натуральных чисел n , а 509203 предположительно является наименьшим двойственным числом Ризеля.
Наименьшее число n, при котором 2 n - k является простым, равно (для нечетных k s, и эта последовательность требует, чтобы 2 n > k )
Нечетные числа k , которые k - 2 n являются составными для всех 2 n < k ( числа де Полиньяка ), равны
Неизвестные значения [ требуется уточнение ] k s равны (для которых 2 n > k )
Можно обобщить задачу Ризеля до целого числа с основанием b ≥ 2. Число Ризеля с основанием b — это положительное целое число k, такое что gcd ( k − 1, b − 1) = 1. (если gcd( k − 1, b − 1) > 1, то gcd( k − 1, b − 1) является тривиальным множителем числа k × b n − 1 (Определение тривиальных множителей для гипотез: каждое n -значение имеет один и тот же множитель)) [5] [6] Для каждого целого числа b ≥ 2 существует бесконечно много чисел Ризеля с основанием b .
Пример 1: Все числа, сравнимые с 84687 mod 10124569 и не сравнимые с 1 mod 5, являются числами Ризеля по основанию 6, из-за покрывающего множества {7, 13, 31, 37, 97}. Кроме того, эти k не являются тривиальными, так как gcd( k + 1, 6 − 1) = 1 для этих k . (Гипотеза Ризеля по основанию 6 не доказана, у нее осталось 3 k , а именно 1597, 9582 и 57492)
Пример 2: 6 — число Ризеля по всем основаниям b, сравнимое с 34 mod 35, потому что если b сравнимо с 34 mod 35, то 6× b n − 1 делится на 5 для всех четных n и делится на 7 для всех нечетных n . Кроме того, 6 не является тривиальным k по этим основаниям b, так как gcd(6 − 1, b − 1) = 1 для этих оснований b .
Пример 3: Все квадраты k, сравнимые с 12 mod 13 и не сравнимые с 1 mod 11, являются числами Ризеля по основанию 12, поскольку для всех таких k , k ×12 n − 1 имеет алгебраические множители для всех четных n и делится на 13 для всех нечетных n . Кроме того, эти k не являются тривиальными, поскольку gcd( k + 1, 12 − 1) = 1 для этих k . (Гипотеза Ризеля по основанию 12 доказана)
Пример 4: Если k находится между кратным 5 и кратным 11, то k × 109 n − 1 делится либо на 5, либо на 11 для всех положительных целых чисел n . Первые несколько таких k — это 21, 34, 76, 89, 131, 144, ... Однако все эти k < 144 также являются тривиальными k (т. е. gcd( k − 1, 109 − 1) не равен 1). Таким образом, наименьшее число Ризеля с основанием 109 — это 144. (Гипотеза Ризеля с основанием 109 не доказана, у нее осталось одно k , а именно 84)
Пример 5: Если k — квадрат, то k ×49 n − 1 имеет алгебраические множители для всех положительных целых чисел n . Первые несколько положительных квадратов — это 1, 4, 9, 16, 25, 36, ... Однако все эти k < 36 также являются тривиальными k (т. е. gcd( k − 1, 49 − 1) не равно 1). Таким образом, наименьшее число Ризеля с основанием 49 — это 36. (Гипотеза Ризеля с основанием 49 доказана)
Мы хотим найти и доказать наименьшее число Ризеля по основанию b для каждого целого числа b ≥ 2. Предполагается, что если k — число Ризеля по основанию b , то выполняется по крайней мере одно из трех условий:
В следующем списке мы рассматриваем только те положительные целые числа k, для которых gcd( k − 1, b − 1) = 1, и все целые числа n должны быть ≥ 1.
Примечание: k -значения, кратные b , где k −1 не является простым числом, включены в гипотезы (и включены в оставшиеся k с красным цветом, если для этих k -значений простые числа неизвестны ), но исключены из проверки (таким образом, они никогда не будут k из «найденных 5 наибольших простых чисел»), поскольку такие k -значения будут иметь то же самое простое число, что и k / b .
б | предполагаемый наименьший Riesel k | покрывающий набор / алгебраические факторы | оставшиеся k без известных простых чисел (красный цвет обозначает k -значения, кратные b , а k −1 не является простым числом) | количество оставшихся k без известных простых чисел (исключая красные k ) | предел тестирования n (исключая красный k s) | Найдено 5 наибольших простых чисел (исключая красные k ) |
2 | 509203 | {3, 5, 7, 13, 17, 241} | 23669, 31859, 38473, 46663, 47338 , 63718 , 67117, 74699, 76946, 81041 , 93326 , 94676 , 107347, 121889, 127436, 129007, 134234 , 143047 , 149398 , 153892 , 161669, 162082 , 186652 , 189352 , 206231, 214694 , 215443, 226153, 234343, 243778 , 245561, 250027, 254872 , 258014, 268468 , 286094 , 298796 , 307784 , 315929 , 319511, 323338, 324011 , 324164, 325123 , 32 7671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 373304 , 384539, 386801, 388556 , 397027, 409753, 412462 , 429388 , 430886 , 444637, 452306 , 468686 , 470173, 474491, 477583, 485557, 487556 , 491122 , 494743, 500 054 | 42 | PrimeGrid в настоящее время ищет все оставшиеся k при n > 14,5M | 97139×2 18397548 –1 93839×2 15337656 –1 192971×2 14773498 –1 206039×2 13104952 –1 2293×2 12918431 –1 |
3 | 63064644938 | {5, 7, 13, 17, 19, 37, 41, 193, 757} | 3677878, 6878756, 10463066, 10789522, 11033634, 16874152 , 18137648, 20636268 , 21368582, 29140796, 31064666, 31389198 , 3 2368566 , 33100902 , 38394682, 40175404, 40396658, 50622456, 51672206, 52072432 , 54412944 , 56244334 , 59254534, 61908864 , 62126002, 62402206, 64105746 , 65337866, 71248336, 87422388 , 93193998, 94167594 , 94210372 , 97105698 , 976211 24, 99302706 , 103101766, 103528408, 107735486, 111036578, 115125596, 115184046 , ... | 100714 | k = 3677878 при n = 5M, 4M < k ≤ 2,147G при n = 1,07M, 2,147G < k ≤ 6G при n = 500K, 6G < k ≤ 10G при n = 250K, 10G < k ≤ 63G при n = 100K, , k > 63G при n = 655K | 676373272×3 1072675 −1 |
4 | 9 | 9× 4n − 1 = (3×2n − 1) × (3×2n + 1) | нет (доказано) | 0 | − | 8×4 1 –1 6×4 1 –1 5×4 1 –1 3×4 1 –1 2×4 1 –1 |
5 | 346802 | {3, 7, 13, 31, 601} | 4906, 23906, 24530 , 26222, 35248, 68132, 71146, 76354, 81134, 92936, 102952, 109238, 109862, 119530, 122650 , 127174 , 13 1110 , 131848, 134266, 143632, 145462, 145484, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 176240 , 179080 , 182398, 187916, 189766, 190334, 195872, 201778, 204394, 206894, 231674, 239062, 239342, 246238, 248546, 259072, 264610, 265702, 267298, 271162, 285598, 285728 , 298442, 304004, 313126, 318278, 325922, 335414, 338866, 340660 | 54 | PrimeGrid в настоящее время ищет все оставшиеся k при n > 4,8M | 3622×5 7558139 -1 136804×5 4777253 -1 |
6 | 84687 | {7, 13, 31, 37, 97} | 1597, 9582 , 57492 | 1 | 5М | 36772×6 1723287 –1 43994×6 569498 –1 77743×6 560745 –1 51017×6 528803 –1 57023×6 483561 –1 |
7 | 408034255082 | {5, 13, 19, 43, 73, 181, 193, 1201} | 315768, 1356018 , 2210376 , 2494112, 2631672, 3423408, 4322834, 4326672, 4363418, 4382984, 4870566, 4990788, 5529368, 62790 74, 6463028, 6544614, 7446728, 7553594, 8057622, 8354966, 8389476, 8640204, 8733908, 9492126 , 9829784, 10096364, 10098716, 10243424, 10289166, 10394778, 10494794, 10965842, 11250728, 11335962, 11372214, 11522846, 11684954, 11943810, 11 952888, 11983634, 12017634, 12065672, 12186164, 12269808, 12291728, 12801926, 13190732, 13264728, 13321148, 13635266, 13976426, ... | 16399 к с ≤ 1G | k ≤ 2M при n = 1M, 2M < k ≤ 10M при n = 500K, 10M < k ≤ 110M при n = 150K, 110M < k ≤ 300M при n = 100K, 300M < k ≤ 1G при n = 25K | 1620198×7 684923 −1 7030248×7 483691 −1 7320606×7 464761 −1 5646066×7 460533 −1 9012942×7 425310 −1 |
8 | 14 | {3, 5, 13} | нет (доказано) | 0 | − | 11×8 18 –1 5×8 4 –1 12×8 3 –1 7×8 3 –1 2×8 2 –1 |
9 | 4 | 4×9 n − 1 = (2×3 n − 1) × (2×3 n + 1) | нет (доказано) | 0 | − | 2×9 1 −1 |
10 | 10176 | {7, 11, 13, 37} | 4421 | 1 | 1.72M | 7019×10 881309 –1 8579×10 373260 –1 6665×10 60248 –1 1935×10 51836 –1 1803×10 45882 –1 |
11 | 862 | {3, 7, 19, 37} | нет (доказано) | 0 | − | 62×11 26202 –1 308×11 444 –1 172×11 187 –1 284×11 186 –1 518×11 78 –1 |
12 | 25 | {13} для нечетных n , 25×12 n − 1 = (5×12 n /2 − 1) × (5×12 n /2 + 1) для четных n | нет (доказано) | 0 | − | 24×12 4 –1 18×12 2 –1 17×12 2 –1 13×12 2 –1 10×12 2 –1 |
13 | 302 | {5, 7, 17} | нет (доказано) | 0 | − | 288×13 109217 –1 146×13 30 –1 92×13 23 –1 102×13 20 –1 300×13 10 –1 |
14 | 4 | {3, 5} | нет (доказано) | 0 | − | 2×14 4 −1 3×14 1 −1 |
15 | 36370321851498 | {13, 17, 113, 211, 241, 1489, 3877} | 381714, 4502952, 5237186, 5725710 , 7256276, 8524154, 11118550, 11176190, 12232180, 15691976, 16338798, 16695396, 18267324 , 18709072, 19615792, ... | 14 тыс. с ≤ 20 млн. | k ≤ 10M при n = 1M, 10M < k ≤ 20M при n = 250K | 4242104×15 728840 –1 9756404×15 527590 –1 9105446×15 496499 –1 5854146×15 428616 –1 9535278×15 375675 –1 |
16 | 9 | 9×16 n − 1 = (3×4 n − 1) × (3×4 n + 1) | нет (доказано) | 0 | − | 8 ×16 1–1 5×16 1–1 3 ×16 1–1 2 × 16 1–1 |
17 | 86 | {3, 5, 29} | нет (доказано) | 0 | − | 44×17 6488 –1 36×17 243 –1 10×17 117 –1 26×17 110 –1 58×17 35 –1 |
18 | 246 | {5, 13, 19} | нет (доказано) | 0 | − | 151×18 418 –1 78×18 172 –1 50×18 110 –1 79×18 63 –1 237×18 44 –1 |
19 | 144 | {5} для нечетных n , 144×19 n − 1 = (12×19 n /2 − 1) × (12×19 n /2 + 1) для четных n | нет (доказано) | 0 | − | 134×19 202 –1 104×19 18 –1 38×19 11 –1 128×19 10 –1 108×19 6 –1 |
20 | 8 | {3, 7} | нет (доказано) | 0 | − | 2×20 10 –1 6×20 2 –1 5×20 2 –1 7×20 1 –1 3×20 1 –1 |
21 | 560 | {11, 13, 17} | нет (доказано) | 0 | − | 64×21 2867 –1 494×21 978 –1 154×21 103 –1 84×21 88 –1 142×21 48 –1 |
22 | 4461 | {5, 23, 97} | 3656 | 1 | 2М | 3104×22 161188 –1 4001×22 36614 –1 2853×22 27975 –1 1013×22 26067 –1 4118×22 12347 –1 |
23 | 476 | {3, 5, 53} | 404 | 1 | 1.35M | 194×23 211140 –1 134×23 27932 –1 394×23 20169 –1 314×23 17268 –1 464×23 7548 –1 |
24 | 4 | {5} для нечетных n , 4×24 n − 1 = (2×24 n /2 − 1) × (2×24 n /2 + 1) для четных n | нет (доказано) | 0 | − | 3×24 1 −1 2×24 1 −1 |
25 | 36 | 36×25 n − 1 = (6×5 n − 1) × (6×5 n + 1) | нет (доказано) | 0 | − | 32×25 4–1 30×25 2–1 26× 25 2–1 12 × 25 2–1 2 × 25 2–1 |
26 | 149 | {3, 7, 31, 37} | нет (доказано) | 0 | − | 115×26 520277 –1 32×26 9812 –1 73×26 537 –1 80×26 382 –1 128×26 300 –1 |
27 | 8 | 8×27 n − 1 = (2×3 n − 1) × (4×9 n + 2×3 n + 1) | нет (доказано) | 0 | − | 6 ×27 2–1 4 ×27 1–1 2 ×27 1–1 |
28 | 144 | {29} для нечетных n , 144×28 n − 1 = (12×28 n /2 − 1) × (12×28 n /2 + 1) для четных n | нет (доказано) | 0 | − | 107×28 74 –1 122×28 71 –1 101×28 53 –1 14×28 47 –1 90×28 36 –1 |
29 | 4 | {3, 5} | нет (доказано) | 0 | − | 2×29 136 −1 |
30 | 1369 | {7, 13, 19} для нечетных n , 1369×30 n − 1 = (37×30 n /2 − 1) × (37×30 n /2 + 1) для четных n | 659, 1024 | 2 | 500К | 239×30 337990 –1 249×30 199355 –1 225×30 158755 –1 774×30 148344 –1 25×30 34205 –1 |
31 | 134718 | {7, 13, 19, 37, 331} | 55758 | 1 | 3М | 6962×31 2863120 –1 126072×31 374323 –1 43902×31 251859 –1 55940×31 197599 –1 101022×31 133208 –1 |
32 | 10 | {3, 11} | нет (доказано) | 0 | − | 3×32 11–1 2 ×32 6–1 9×32 3–1 8 × 32 2–1 5 × 32 2–1 |
Предполагаемое наименьшее число Ризеля с основанием n равно (начнем с n = 2)