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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел нечётное натуральное число 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 является простым.

Известные числа Серпинского[править | править исходный текст]

Последовательность известных на данный момент чисел Серпинского начинается так: 78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, 1259779, 1290677, 1518781, 1624097, 1639459, 1777613, 2131043, 2131099, 2191531, 2510177, 2541601, 2576089, 2931767, 2931991, 3083723, 3098059, 3555593, 3608251 … (последовательность A076336 в OEIS)

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

Проблема Серпинского[править | править исходный текст]

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

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

На декабрь 2013 года оставалось лишь шесть чисел-кандидатов, которые могли бы опровергнуть эту гипотезу: 10223, 21181, 22699, 24737, 55459 и 67607[2].

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]

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