Числа Серпинского

В теории чисел нечётное натуральное число k является числом Серпинского, если для любого натурального числа n число $k\cdot 2^{n}+1$ является составным. Числа Серпинского названы так в честь открывшего их существование польского математика Вацлава Серпинского.

Существование чисел Серпинского довольно неочевидно. Например, если рассмотреть последовательность $3\cdot 2^{n}+1$ , то в ней регулярно будут встречаться простые числа, и неожиданным является тот факт, что для некоторых k в последовательности $k\cdot 2^{n}+1$ никогда не встретится простое число.

Чтобы доказать, что число k не является числом Серпинского, нужно найти такое n, что число $k\cdot 2^{n}+1$ является простым.

Известные числа Серпинского

Последовательность известных на данный момент чисел Серпинского начинается так[1]:

78 557, 271 129, 271 577, 322 523, 327 739, 482 719, 575 041, 603 713, 903 983, 934 909, 965 431, 1 259 779, 1 290 677, 1 518 781, 1 624 097, 1 639 459, 1 777 613, 2 131 043, 2 131 099, 2 191 531, 2 510 177, 2 541 601, 2 576 089, 2 931 767, 2 931 991, 3 083 723, 3 098 059, 3 555 593, 3 608 251, …

То, что число 78 557 является числом Серпинского, было доказано в 1962 году Джоном Селфриджом, который показал, что каждое число вида $78557\cdot 2^{n}+1$ делится по крайней мере на одно число из покрывающего множества {3, 5, 7, 13, 19, 37, 73}. Аналогично доказывается, что 271 129 также является числом Серпинского: каждое число вида $271129\cdot 2^{n}+1$ делится по крайней мере на одно число из множества {3, 5, 7, 13, 17, 241}. Большинство известных на данный момент чисел Серпинского обладают подобными покрывающими множествами[2].

Проблема Серпинского

Задача отыскания минимального числа Серпинского известна как проблема Серпинского.

В 1967 году Селфридж и Серпинский предположили, что 78 557 является наименьшим числом Серпинского. Доказательством этой гипотезы занимаются проекты распределённых вычислений Seventeen or Bust и PrimeGrid.

К концу 2016 года из шести чисел-кандидатов, которые могли бы опровергнуть эту гипотезу, осталось пять: 21 181, 22 699, 24 737, 55 459 и 67 607[3] (число 10223 было отвергнуто в ноябре 2016 года[4]).

См. также

Число Прота

Примечания

Последовательность A076336 в OEIS: числа Серпинского = (Provable) Sierpiński numbers: odd numbers n such that for all k >= 1 the numbers n*2^k + 1 are composite
Sierpinski number at The Prime Glossary (англ.)
Seventeen or Bust: Project Stats Архивная копия от 24 декабря 2013 на Wayback Machine (англ.)
Найдено одно из самых больших простых чисел, насчитывающее более 9 миллионов знаков

Ссылки

Prime Riddle (англ.) — статья про числа Серпинского и проект Seventeen or Bust.

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

[1] Последовательность A076336 в OEIS: числа Серпинского = (Provable) Sierpiński numbers: odd numbers n such that for all k >= 1 the numbers n*2^k + 1 are composite

[2] Sierpinski number at The Prime Glossary (англ.)

[3] Seventeen or Bust: Project Stats Архивная копия от 24 декабря 2013 на Wayback Machine (англ.)

[4] Найдено одно из самых больших простых чисел, насчитывающее более 9 миллионов знаков