Число Ризеля

Нечетное k такое, что k·2ⁿ − 1 является составным для всех n

В математике число Ризеля — это нечетное натуральное число k , для которого является составным для всех натуральных чисел n (последовательность A101036 в OEIS ). Другими словами, когда k — число Ризеля, все члены следующего множества являются составными: к × 2 н 1 {\displaystyle k\times 2^{n}-1}

{ к × 2 н 1 : н Н } . {\displaystyle \left\{\,k\times 2^{n}-1:n\in \mathbb {N} \,\right\}.}

Если вместо этого используется форма , то kчисло Серпинского . к × 2 н + 1 {\displaystyle k\times 2^{n}+1}

проблема Ризеля

Нерешенная задача по математике :
Является ли 509 203 наименьшим числом Ризеля?

В 1956 году Ганс Ризель показал, что существует бесконечное число целых чисел k, таких, что не является простым для любого целого числа  n . Он показал, что число 509203 обладает этим свойством, как и 509203 плюс любое положительное целое число , кратное 11184810. [1] Задача Ризеля состоит в определении наименьшего числа Ризеля. Поскольку не было найдено покрывающего множества для любого k , меньшего 509203, предполагается , что оно является наименьшим числом Ризеля. к × 2 н 1 {\displaystyle k\times 2^{n}-1}

Чтобы проверить, есть ли 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, 2 45561, 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, 1830187, 1976473, 2136283, 2251349, 2313487, 2344211, 2554843, 2924861, ... (последовательность A101036 в OEIS )

Комплект для покрытия

Число может быть показано как число Ризеля, если показать покрывающий набор : набор простых чисел, который разделит любого члена последовательности, так называемый потому, что он, как говорят, "покрывает" эту последовательность. Единственные доказанные числа Ризеля ниже миллиона имеют покрывающие наборы следующим образом:

  • 509203 × 2 н 1 {\displaystyle 509203\times 2^{n}-1} имеет покрывающий набор {3, 5, 7, 13, 17, 241}
  • 762701 × 2 н 1 {\displaystyle 762701\times 2^{n}-1} имеет покрывающий набор {3, 5, 7, 13, 17, 241}
  • 777149 × 2 н 1 {\displaystyle 777149\times 2^{n}-1} имеет покрывающий набор {3, 5, 7, 13, 19, 37, 73}
  • 790841 × 2 н 1 {\displaystyle 790841\times 2^{n}-1} имеет покрывающий набор {3, 5, 7, 13, 19, 37, 73}
  • 992077 × 2 н 1 {\displaystyle 992077\times 2^{n}-1} имеет покрывающий набор {3, 5, 7, 13, 17, 241}.

Самый маленькийндля которогок· 2н− 1 — простое число

Вот последовательность для k = 1, 2, .... Она определяется следующим образом: это наименьшее n ≥ 0, такое что является простым числом, или −1, если такого простого числа не существует. а ( к ) {\displaystyle а(к)} а ( к ) {\displaystyle а(к)} к 2 н 1 {\displaystyle k\cdot 2^{n}-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, 17855036657007596110949, ... (A076335). [4]

Двойственная задача Ризеля

Двойственные числа Ризеля определяются как нечетные натуральные числа k, такие, что |2 n - k | является составным для всех натуральных чисел n . Существует гипотеза, что набор этих чисел совпадает с набором чисел Ризеля. Например, |2 n - 509203| является составным для всех натуральных чисел n , а 509203 предположительно является наименьшим двойственным числом Ризеля.

Наименьшее число n, при котором 2 n - k является простым, равно (для нечетных k s, и эта последовательность требует, чтобы 2 n > k )

2, 3, 3, 39, 4, 4, 4, 5, 6, 5, 5, 6, 5, 5, 5, 7, 6, 6, 11, 7, 6, 29, 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, 47, 8, 14, 9, 11, 10, 9, 10, 8, 9, 8, 8, ... (последовательность A096502 в OEIS )

Нечетные числа k , которые k - 2 n являются составными для всех 2 n < k ( числа де Полиньяка ), равны

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, ... (последовательность A006285 в OEIS )

Неизвестные значения [ требуется уточнение ] k s равны (для которых 2 n > k )

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

основание числа Ризеляб

Можно обобщить задачу Ризеля до целого числа с основанием 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 , то выполняется по крайней мере одно из трех условий:

  1. Все числа вида k × b n − 1 имеют множитель в некотором покрывающем множестве. (Например, b = 22, k = 4461, тогда все числа вида k × b n − 1 имеют множитель в покрывающем множестве: {5, 23, 97})
  2. k × b n − 1 имеет алгебраические множители. (Например, b = 9, k = 4, тогда k × b n − 1 можно разложить на множители (2×3 n − 1) × (2×3 n + 1))
  3. Для некоторых n числа вида k × b n − 1 имеют множитель в некотором покрывающем множестве; а для всех других n k × b n 1 имеет алгебраические множители. (Например, b = 19, k = 144, тогда, если n нечетное, то k × b n − 1 делится на 5, если n четное, то k × b n − 1 можно разложить на множители (12×19 n /2 − 1) × (12×19 n /2 + 1))

В следующем списке мы рассматриваем только те положительные целые числа 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 )
2509203{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 05442PrimeGrid в настоящее время ищет все оставшиеся k при n > 14,5M97139×2 18397548 –1
93839×2 15337656 –1
192971×2 14773498 –1
206039×2 13104952 –1
2293×2 12918431 –1
363064644938{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 , ...100714k = 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
1068687512×3 1067484 −1
1483575692×3 1067339 −1
780548926×3 1064065 −1
1776322388×3 1053069 −1

494n − 1 = (3×2n 1) × (3×2n + 1)нет (доказано)08×4 1 –1
6×4 1 –1
5×4 1 –1
3×4 1 –1
2×4 1 –1
5346802{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, 34066054PrimeGrid в настоящее время ищет все оставшиеся k при n > 4,8M3622×5 7558139 -1

136804×5 4777253 -1
52922×5 4399812 -1
177742×5 4386703 -1
213988×5 4138363 -1

684687{7, 13, 31, 37, 97}1597, 9582 , 57492136772×6 1723287 –1
43994×6 569498 –1
77743×6 560745 –1
51017×6 528803 –1
57023×6 483561 –1
7408034255082{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 к с ≤ 1Gk ≤ 2M при n = 1M, 2M < k ≤ 10M при n = 500K, 10M < k ≤ 110M при n = 150K, 110M < k ≤ 300M при n = 100K, 300M < k ≤ 1G при n = 25K1620198×7 684923 −1
7030248×7 483691 −1
7320606×7 464761 −1
5646066×7 460533 −1
9012942×7 425310 −1
814{3, 5, 13}нет (доказано)011×8 18 –1
5×8 4 –1
12×8 3 –1
7×8 3 –1
2×8 2 –1
944×9 n − 1 = (2×3 n − 1) × (2×3 n + 1)нет (доказано)02×9 1 −1
1010176{7, 11, 13, 37}442111.72M7019×10 881309 –1
8579×10 373260 –1
6665×10 60248 –1
1935×10 51836 –1
1803×10 45882 –1
11862{3, 7, 19, 37}нет (доказано)062×11 26202 –1
308×11 444 –1
172×11 187 –1
284×11 186 –1
518×11 78 –1
1225{13} для нечетных n , 25×12 n − 1 = (5×12 n /2 − 1) × (5×12 n /2 + 1) для четных nнет (доказано)024×12 4 –1
18×12 2 –1
17×12 2 –1
13×12 2 –1
10×12 2 –1
13302{5, 7, 17}нет (доказано)0288×13 109217 –1
146×13 30 –1
92×13 23 –1
102×13 20 –1
300×13 10 –1
144{3, 5}нет (доказано)02×14 4 −1
3×14 1 −1
1536370321851498{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 = 250K4242104×15 728840 –1
9756404×15 527590 –1
9105446×15 496499 –1
5854146×15 428616 –1
9535278×15 375675 –1
1699×16 n − 1 = (3×4 n − 1) × (3×4 n + 1)нет (доказано)08 ×16 1–1
5×16 1–1 3
×16 1–1 2 ×
16 1–1
1786{3, 5, 29}нет (доказано)044×17 6488 –1
36×17 243 –1
10×17 117 –1
26×17 110 –1
58×17 35 –1
18246{5, 13, 19}нет (доказано)0151×18 418 –1
78×18 172 –1
50×18 110 –1
79×18 63 –1
237×18 44 –1
19144{5} для нечетных n , 144×19 n − 1 = (12×19 n /2 − 1) × (12×19 n /2 + 1) для четных nнет (доказано)0134×19 202 –1
104×19 18 –1
38×19 11 –1
128×19 10 –1
108×19 6 –1
208{3, 7}нет (доказано)02×20 10 –1
6×20 2 –1
5×20 2 –1
7×20 1 –1
3×20 1 –1
21560{11, 13, 17}нет (доказано)064×21 2867 –1
494×21 978 –1
154×21 103 –1
84×21 88 –1
142×21 48 –1
224461{5, 23, 97}365613104×22 161188 –1
4001×22 36614 –1
2853×22 27975 –1
1013×22 26067 –1
4118×22 12347 –1
23476{3, 5, 53}40411.35M194×23 211140 –1
134×23 27932 –1
394×23 20169 –1
314×23 17268 –1
464×23 7548 –1
244{5} для нечетных n , 4×24 n − 1 = (2×24 n /2 − 1) × (2×24 n /2 + 1) для четных nнет (доказано)03×24 1 −1
2×24 1 −1
253636×25 n − 1 = (6×5 n − 1) × (6×5 n + 1)нет (доказано)032×25 4–1
30×25 2–1
26× 25 2–1 12
× 25 2–1 2 ×
25 2–1
26149{3, 7, 31, 37}нет (доказано)0115×26 520277 –1
32×26 9812 –1
73×26 537 –1
80×26 382 –1
128×26 300 –1
2788×27 n − 1 = (2×3 n − 1) × (4×9 n + 2×3 n + 1)нет (доказано)06 ×27 2–1 4
×27 1–1 2
×27 1–1
28144{29} для нечетных n , 144×28 n − 1 = (12×28 n /2 − 1) × (12×28 n /2 + 1) для четных nнет (доказано)0107×28 74 –1
122×28 71 –1
101×28 53 –1
14×28 47 –1
90×28 36 –1
294{3, 5}нет (доказано)02×29 136 −1
301369{7, 13, 19} для нечетных n , 1369×30 n − 1 = (37×30 n /2 − 1) × (37×30 n /2 + 1) для четных n659, 10242500К239×30 337990 –1
249×30 199355 –1
225×30 158755 –1
774×30 148344 –1
25×30 34205 –1
31134718{7, 13, 19, 37, 331}5575816962×31 2863120 –1
126072×31 374323 –1
43902×31 251859 –1
55940×31 197599 –1
101022×31 133208 –1
3210{3, 11}нет (доказано)03×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 )

Смотрите также

Ссылки

  1. ^ Ризель, Ганс (1956). «Награ стора первобытная». Элемента . 39 : 258–260.
  2. ^ "Статистика проблемы Ризеля" . ПраймГрид.
  3. ^ "Статистика проблемы Ризеля". PrimeGrid . Архивировано из оригинала 15 января 2024 года . Получено 15 января 2024 года .
  4. ^ «Задача 29.- Числа Бриера».
  5. ^ «Гипотезы и доказательства Ризеля».
  6. ^ «Гипотезы Ризеля и доказательства степеней двойки».

Источники

  • PrimeGrid
  • Проблема Ризеля: определение и статус
  • Главный глоссарий: число Ризеля
  • Список простых чисел вида: k*2^n-1, k<300
  • Список простых чисел вида: k*2^n-1, k<300, Project Riesel Prime Search
  • База данных Riesel and Proth Prime
Взято с "https://en.wikipedia.org/w/index.php?title=Номер_Ризеля&oldid=1253477078#Проблема_двойного_Ризеля"