Числа Мерсенна

Числа Мерсе́нна — числа вида $M_n = 2^n - 1$, где $n$ — натуральное число. Названы в честь французского математика Марена Мерсенна.

Последовательность чисел Мерсенна начинается так:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, … (последовательность A000225 в OEIS)

Иногда числами Мерсенна называют числа $M_p$ с простыми индексами p. Эта последовательность начинается так:

3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, … (последовательность A001348 в OEIS)

Множества простых чисел в этих последовательностях совпадает, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.

Свойства

• Если $M_n$ является простым, то число n также простое.
• Любой делитель числа $M_p$ для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
• Каждое чётное совершенное число имеет вид $\tfrac{M_p(M_p+1)}{2}=2^{p-1}(2^p - 1)$, где число Мерсенна $M_p$ является простым (доказано Эйлером).

Простые числа Мерсенна

Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые больши́е известные простые числа.

На февраль 2013 года самым больши́м известным простым числом является число Мерсенна $M_{57885161} = 2^{57885161} - 1$, найденное в январе 2013 года в рамках проекта распределённых вычислений GIMPS. Десятичная запись числа $M_{57885161}$ содержит 17425170 цифр.

Всего известно 48 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 42. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

Простые числа Мерсенна и их показатели образуют последовательности:

$M_p$: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727, … (последовательность A000668 в OEIS)

p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, … (последовательность A000043 в OEIS)

За нахождение 45-го простого числа Мерсена $M_{43112609}$ проектом GIMPS в 2009 году была получена премия в 100 000 долларов США, назначенная сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.

Вариации и обобщения

• Двойные числа Мерсенна определяются как $MM_n = M_{M_n} = 2^{2^n - 1} - 1$.

Открытые проблемы

• Бесконечность количества простых чисел Мерсенна и их асимптотика.
• Простота числа $M_{M_{61}} = 2^{2^{61} - 1} - 1$.

Применение

На практике простые числа Мерсенна применяются для построения генераторов псевдо-случайных чисел с большими периодами, таких, как вихрь Мерсенна.

Ссылки

• Weisstein, Eric W. Mersenne Number (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Double Mersenne Numbers (англ.) на сайте Wolfram MathWorld.
• Андрей Коняев Проще некуда. Найдено простое число длиной в пять романов «Война и мир» // lenta.ru. — 12 февраля 2013.