Число Ризеля
В математике число Ризеля — это нечетное натуральное число 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 , равны
- 23669, 31859, 38473, 46663, 67117, 74699, 81041, 107347, 121889, 129007, 143047, 161669, 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.
Последнее исключение произошло в апреле 2023 года, когда 97139 × 2 18397548 − Райан Проппер обнаружил, что 1 является простым. Это число состоит из 5 538 219 цифр.
По состоянию на январь 2023 года PrimeGrid провел поиск оставшихся кандидатов до n = 14 900 000. [3]
Известные числа Ризеля
[ редактировать ]Последовательность известных на данный момент чисел Ризеля начинается с:
- 509203, 762701, 777149, 790841, 992077, 1106681, 1247173, 1254341, 1330207, 1330319, 1715053, 1730653, 1730681, 1744117, 1 830187, 1976473, 2136283, 2251349, 2313487, 2344211, 2554843, 2924861, ... (последовательность A101036 в ОЭИС )
Комплект чехлов
[ редактировать ]Можно показать, что число является числом Ризеля, продемонстрировав покрывающее множество : набор простых чисел, которые делят любой член последовательности, называемой так потому, что говорят, что она «покрывает» эту последовательность. Единственные проверенные числа Ризеля ниже миллиона имеют следующие наборы покрытия:
- имеет покрывающее множество {3, 5, 7, 13, 17, 241}
- имеет покрывающее множество {3, 5, 7, 13, 17, 241}
- имеет покрывающее множество {3, 5, 7, 13, 19, 37, 73}
- имеет покрывающее множество {3, 5, 7, 13, 19, 37, 73}
- имеет покрывающее множество {3, 5, 7, 13, 17, 241}.
Наименьшее n, для которого k · 2 н − 1 — простое число
[ редактировать ]Вот последовательность для k = 1, 2, .... Он определяется следующим образом: — наименьшее n ≥ 0 такое, что является простым или -1, если такого простого числа не существует.
- 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, ... (последовательность A040081 в OEIS ). Первое неизвестное n для этого k = 23669.
Связанными последовательностями являются OEIS : A050412 (не допускается n = 0), для нечетных k см. OEIS : A046069 или OEIS : A108129 (не допускается n = 0).
Одновременно Ризель и Серпинский
[ редактировать ]Рядом может быть одновременно Ризель и Серпинский . Это так называемые числа Брайера. Пять самых маленьких известных примеров: 3316923598096294713661, 10439679896374780276373, 11615103277955704975673, 12607110588854501953787, 17855036657007596. 110949,... ( А076335 ). [4]
Проблема двойной струйки
[ редактировать ]Двойственные числа Ризеля определяются как нечетные натуральные числа k такие, что |2 н - к | является составным для всех натуральных чисел n . Существует гипотеза, что набор этих чисел такой же, как набор чисел Ризеля. Например, |2 н - 509203| является составным для всех натуральных чисел n , а 509203 предполагается как наименьшее двойственное число Ризеля.
Наименьшее n, которое 2 н - k простое число (для нечетных k s, и эта последовательность требует, чтобы 2 н > к )
- 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, ... (последовательность A096502 в OEIS )
Нечетное k s, которое k - 2 н все составные для всех 2 н < k ( числа де Полиньяка ) равны
- 1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, , 1259, 1271, 1477, ... (последовательность A006285 в OEIS )
Неизвестные значения [ нужны разъяснения ] из k s (для которых 2 н > к )
- 1871, 2293, 25229, 31511, 36971, 47107, 48959, 50171, 56351, 63431, 69427, 75989, 81253, 83381, 84491, ...
Числовая база Ризеля b
[ редактировать ]Можно обобщить проблему Ризеля на целочисленную базу b ≥ 2. База чисел Ризеля b — это целое положительное число k такое, что gcd ( k − 1, b − 1) = 1. (если gcd( k − 1, b − 1 ) > 1, то НОД( k − 1, b − 1) является тривиальным множителем k × b н − 1 (Определение тривиальных факторов для гипотез: каждое n -значение имеет один и тот же фактор)) [5] [6] Для каждого целого числа b ≥ 2 существует бесконечно много чисел Ризеля по основанию b .
Пример 1: Все числа, конгруэнтные 84687 по модулю 10124569 и не конгруэнтные 1 по модулю 5, являются числами Ризеля по основанию 6 из-за покрывающего множества {7, 13, 31, 37, 97}. Кроме того, эти k нетривиальны, поскольку для них gcd( + 1, 6 − 1) = 1 k . (Гипотеза Ризеля о основании 6 не доказана, у нее осталось 3 k , а именно 1597, 9582 и 57492)
Пример 2: 6 — число Ризеля по всем основаниям b, соответствующее 34 по модулю 35, потому что если b соответствует 34 по модулю 35, то 6 × b н − 1 делится на 5 для всех четных n и делится на 7 для всех нечетных n . Кроме того, 6 не является тривиальным k в этих базисах b, поскольку НОД(6 - 1, b - 1) = 1 для этих базисов b .
Пример 3: Все квадраты k, конгруэнтные 12 по модулю 13 и не конгруэнтные 1 по модулю 11, являются числами Ризеля по основанию 12, поскольку для всех таких k , k ×12 н − 1 имеет алгебраические множители для всех четных n и делится на 13 для всех нечетных n . Кроме того, эти k нетривиальны, поскольку для них НОД( + 1, 12 − 1) = 1 k . (Гипотеза Ризеля о основании 12 доказана)
Пример 4: Если k находится в диапазоне от кратного 5 до кратного 11, то k ×109. н − 1 делится на 5 или 11 для всех натуральных чисел n . Первые несколько таких k — это 21, 34, 76, 89, 131, 144, ... Однако все эти k < 144 также являются тривиальными k (т.е. НОД( k - 1, 109 - 1) не равен 1). Таким образом, наименьшее основание числа Ризеля 109 равно 144. (Гипотеза Ризеля по основанию 109 не доказана, у нее осталось одно k , а именно 84)
Пример 5: Если k квадратное, то k ×49 н − 1 имеет алгебраические множители для всех натуральных чисел n . Первые несколько положительных квадратов — это 1, 4, 9, 16, 25, 36, ... Однако все эти k < 36 также являются тривиальными k (т.е. НОД ( k - 1, 49 - 1) не равен 1). Таким образом, наименьшее число Ризеля по основанию 49 равно 36. (Гипотеза Ризеля по основанию 49 доказана)
Мы хотим найти и доказать наименьшую базу чисел Ризеля b для каждого целого числа b ≥ 2. Это гипотеза, что если k является базой чисел Ризеля b , то выполняется хотя бы одно из трех условий:
- Все числа вида k × b н − 1 имеют фактор в некотором покрывающем множестве. (Например, b = 22, k = 4461, тогда все числа вида k × b н − 1 имеют фактор в покрывающем множестве: {5, 23, 97})
- k × b н − 1 имеет алгебраические множители. (Например, b = 9, k = 4, тогда k × b н − 1 можно разложить на (2×3 н − 1) × (2×3 н + 1))
- Для некоторого n числа вида k × b н − 1 имеют фактор в некотором покрывающем множестве; а для всех остальных n , k × b н − 1 имеет алгебраические множители. (Например, b = 19, k = 144, тогда если n нечетное, то k × b н − 1 делится на 5, если n четное, то k × b н − 1 можно разложить на (12×19 н /2 − 1) × (12×19 н /2 + 1))
В следующем списке мы рассматриваем только те положительные целые числа k, для которых НОД( k - 1, b - 1) = 1, и все целые числа n должны быть ≥ 1.
Примечание: значения k , кратные b и где k −1 не является простым, включаются в гипотезы (и включаются в оставшиеся k с красный -значений не известны простые числа цвет, если для этих k ), но исключаются из тестирования (таким образом, никогда не должно быть k из «пяти крупнейших найденных простых чисел»), поскольку такие k -значения будут иметь то же простое число, что и k / b .
б | предполагаемый наименьший Ризель k | покрывающее множество / алгебраические факторы | оставшееся k без известных простых чисел (красным обозначены значения k , кратные b , а k -1 не является простым числом) | количество оставшихся k без известных простых чисел (исключая красные буквы ) | предел тестирования n (исключая красные буквы ) | найдены 5 крупнейших простых чисел (исключая красные буквы ) |
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, 327671, 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, 500054 | 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 , 32368566 , 33100902 , 38394682, 40175404, 40396658, 50622456 , 51672206, 52072432, 54412944 , 56244334, 59254534, 61908864 , 62126002, 62402206, 64105746 , 65337866, 71248336, 87422388 , 93193998 , 94167594 , 94210372, 97105698 , 97621124, 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×4 н − 1 = (3×2 н − 1) × (3×2 н + 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, 131110 , 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, 6279074, 6463028, 6544614, 7446728, 7553594, 8057622, 8354966, 8389476, 8640204, 8733908, 9492126 , 9829784, 10096364, 10098716, 10243424, 10289166, 10394778, 10494794, 10965842, 11250728, 11335962, 11372214, 11522846, 11684954, 11943810, 11952888, 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 н − 1 = (2×3 н − 1) × (2×3 н + 1) | нет (доказано) | 0 | − | 2×9 1 −1 |
10 | 10176 | {7, 11, 13, 37} | 4421 | 1 | 1,72 млн. | 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 н − 1 = (5×12 н /2 − 1) × (5×12 н /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 тыс. с ≤ 20M | 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 н − 1 = (3×4 н − 1) × (3×4 н + 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 н − 1 = (12×19 н /2 − 1) × (12×19 н /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,35 М | 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 н − 1 = (2×24 н /2 − 1) × (2×24 н /2 + 1) для четного n | нет (доказано) | 0 | − | 3×24 1 −1 2×24 1 −1 |
25 | 36 | 36×25 н − 1 = (6×5 н − 1) × (6×5 н + 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 н − 1 = (2×3 н − 1) × (4×9 н + 2×3 н + 1) | нет (доказано) | 0 | − | 6×27 2 −1 4×27 1 −1 2×27 1 −1 |
28 | 144 | {29} для нечетного n , 144×28 н − 1 = (12×28 н /2 − 1) × (12×28 н /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 н − 1 = (37×30 н /2 − 1) × (37×30 н /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 | 3M | 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).
- 509203, 63064644938, 9, 346802, 84687, 408034255082, 14, 4, 10176, 862, 25, 302, 4, 36370321851498, 9, 86, 246, 144, 8, 0, 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, ... (последовательность A273987 в OEIS )
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Ризель, Ганс (1956). «Некоторые большие простые числа». Элементы . 39 : 258–260.
- ^ «Статистика проблемы Ризеля» . ПраймГрид.
- ^ «Статистика проблемы Ризеля» . ПраймГрид . Архивировано из оригинала 15 января 2024 года . Проверено 15 января 2024 г.
- ^ «Задача 29. — Числа Брайера» .
- ^ «Гипотезы и доказательства Ризеля» .
- ^ «Гипотезы Ризеля и доказательства степени двойки» .
Источники
[ редактировать ]- Гай, Ричард К. (2004). Нерешенные проблемы теории чисел . Берлин: Springer-Verlag . п. 120. ИСБН 0-387-20860-7 .
- Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел . Нью-Йорк: Springer-Verlag . стр. 357–358 . ISBN 0-387-94457-5 .