Числа Мерсенна - NiNa.Az

Число Мерсе́нна — число вида ${\displaystyle M_{n}=2^{n}-1}$, где ${\displaystyle n}$ — натуральное число; некоторые из таких чисел являются простыми при больших значениях ${\displaystyle n}$. Названы в честь французского математика Маре́на Мерсенна, исследовавшего их свойства в XVII веке.

Первые числа Мерсенна:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16 383, 32 767, 65 535, 131 071, ...

Свойства

Для всех ${\displaystyle M_{n}}$ справедливо следующее: если ${\displaystyle n}$ составное, ${\displaystyle n=kl,k,l>1}$, то и ${\displaystyle M_{n}}$ тоже составное, что следует из разложения:

${\displaystyle 2^{n}-1=2^{kl}-1=(2^{k}-1)(2^{k(l-1)}+2^{k(l-2)}+\dots +1),}$.

Отсюда сразу следует: число ${\displaystyle M_{n}}$ является простым, только если число ${\displaystyle n}$ также простое. Обратное утверждение в общем случае неверно, наименьшим контрпримером является ${\displaystyle M_{11}=2047=23\cdot 89}$.

Любой делитель составного числа ${\displaystyle M_{p}}$ для простого ${\displaystyle p}$ имеет вид ${\displaystyle 2\cdot p\cdot k+1}$, где ${\displaystyle k}$ — натуральное число (это является следствием малой теоремы Ферма).

Простые числа Мерсенна тесно связаны с совершенными числами. Евклид показал, что число вида ${\displaystyle {\tfrac {M_{p}(M_{p}+1)}{2}}=2^{p-1}(2^{p}-1)}$, где число Мерсенна ${\displaystyle M_{p}}$ — простое, является совершенным. Эйлер доказал, что все чётные совершенные числа исчерпываются этой формулой (что касается нечётных совершенных чисел, то до сих пор ничего не известно об их существовании).

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

Для всех простых чисел вида ${\displaystyle 2^{n}-1}$ показатель степени ${\displaystyle n}$ также всегда является простым числом, поэтому особо изучаются числа Мерсенна ${\displaystyle M_{p}=2^{p}-1}$ с простым показателем ${\displaystyle p}$ (в некоторых работах только такие числа считаются числами Мерсенна). Последовательность простых чисел Мерсенна начинается так:

3, 7, 31, 127, 8191, 131 071, 524 287, 2 147 483 647, 2 305 843 009 213 694 000, 618 970 019 642 690 200 000 000 000, 162 259 276 829 213 360 000 000 000 000 000, 170 141 183 460 469 230 000 000 000 000 000 000 000…

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

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11 213, 19 937, 21 701, 23 209, 44 497, 86 243, 110 503, 132 049, 216 091, 756 839, 859 433, 1 257 787, 1 398 269, 2 976 221, 3 021 377, 6 972 593, 13 466 917, 20 996 011, 24 036 583, 25 964 951, 30 402 457, 32 582 657, 37 156 667, 42 643 801, 43 112 609, 57 885 161, 74 207 281, 77 232 917, 82 589 933, 136 279 841…

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

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

По состоянию на 2025 год самым больши́м известным простым числом является число Мерсенна ${\displaystyle 2^{136279841}-1}$, найденное 12 октября 2024 года Люком Дюрантом в рамках проекта добровольных вычислений GIMPS. Десятичная запись числа содержит 41 024 320 цифр.

Всего на 2025 год известно 52 простых числа Мерсенна, при этом порядковые номера достоверно установлены только у первых 49 чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного. При этом 45-е простое число Мерсенна ${\displaystyle M_{37156667}}$ было найдено на две недели позднее 47-го известного простого числа Мерсенна ${\displaystyle M_{43112609}}$, а 46-е известное простое число Мерсенна ${\displaystyle M_{42643801}}$ было найдено только через год.

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

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

Запрос «Двойное число Мерсенна»^[d] перенаправляется сюда. На эту тему нужно создать отдельную статью.

Запрос «Число Каталана — Мерсенна» перенаправляется сюда. На эту тему нужно создать отдельную статью.

Двойное число Мерсенна — число вида ${\displaystyle M_{M_{n}}=2^{2^{n}-1}-1}$. На 2025 год известны только 4 простых числа такого вида (при ${\displaystyle n=2,3,5,7}$).

Число Каталана — Мерсенна — член последовательности чисел, начинающейся с 2 и строящейся путём применения функции ${\displaystyle 2^{n}-1}$ к предыдущему члену ${\displaystyle n}$; первые элементы:

2, 3, 7, 127, 170141183460469231731687303715884105727…

Каталан предполагал, что эти числа просты «вплоть до некоторого предела».

Обобщённое число Мерсенна — число вида:

${\displaystyle h^{0}+h^{1}+h^{2}+\dots +h^{n-1}={\frac {h^{n}-1}{h-1}}=M_{h,n}}$.

Такое обобщение связано с тем, что ${\displaystyle 2^{n}-1}$ можно представить в виде суммы ${\displaystyle n}$ первых членов возрастающей геометрической прогрессии:

${\displaystyle 2^{n}-1=2^{0}+2^{1}+2^{2}+\dots +2^{n-1}={\frac {2^{n}-1}{2-1}}}$,

иными словами, числа Мерсенна являются частным случаем обобщённых чисел Мерсенна при ${\displaystyle h=2}$. При некоторых значениях ${\displaystyle h}$ и ${\displaystyle n}$ обобщённые числа Мерсенна являются простыми, например, ${\displaystyle M_{3,3}}$, ${\displaystyle M_{3,7}}$, ${\displaystyle M_{3,13}}$, ${\displaystyle M_{3,71}}$, ${\displaystyle M_{5,3}}$, ${\displaystyle M_{5,7}}$, ${\displaystyle M_{5,47}}$ и ряд других.

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

Неизвестно, конечно или бесконечно множество простых чисел Мерсенна.

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

Неизвестно, существуют ли простые числа Каталана — Мерсенна при ${\displaystyle n>4}$.

Неизвестно, существуют ли простые двойные числа Мерсенна при ${\displaystyle n>7}$.

См. также

• Наибольшее известное простое число
• GIMPS

Примечания

1. последовательность A000225 в OEIS
2. последовательность A001348 в OEIS
3. последовательность A000668 в OEIS
4. последовательность A000043 в OEIS
5. List of Known Mersenne Prime Numbers (англ.). Great Internet Mersenne Prime Search. Дата обращения: 9 декабря 2016. Архивировано 15 марта 2016 года.
6. The Largest Known Primes--A Summary (англ.). The Prime Pages (26 декабря 2018). Дата обращения: 28 декабря 2018. Архивировано 22 ноября 2008 года.
7. R. P. Brent, P. Zimmermann. Random number generators with period divisible by a Mersenne prime // Lecture Notes in Computer Science. — 2003. — Т. 2667. — С. 1—10. Архивировано 20 марта 2012 года.
8. Matsumoto, Nishimura, 2017.
9. GIMPS Project Discovers Largest Known Prime Number: 2^136,279,841-1  (неопр.). Mersenne Research, Inc. (21 октября 2024). Дата обращения: 21 октября 2024. Архивировано 23 октября 2024 года.
10. GPU победил математику: найдено рекордное простое число из 41млн цифр  (неопр.). SecurityLab.ru (21 октября 2024). Дата обращения: 21 октября 2024. Архивировано 6 ноября 2024 года.
11. GIMPS Milestones  (неопр.). www.mersenne.org. Дата обращения: 5 апреля 2022. Архивировано 13 октября 2021 года.
12. Record 12-Million-Digit Prime Number Nets $100,000 Prize Архивная копия от 26 декабря 2021 на Wayback Machine (англ.)
13. последовательность A007013 в OEIS

Ссылки

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