Просмотр кода страницы Число Мерсенна

'''Число Мерсе́нна''' — число вида <math>M_n = 2^n - 1</math>, где <math>n</math> — [[натуральное число]]; некоторые из таких чисел являются [[Простое число|простыми]] при больших значениях <math>n</math>. Названы в честь французского математика [[Мерсенн, Марен|Маре́на Мерсенна]], исследовавшего их свойства в XVII веке.

Первые числа Мерсенна<ref>{{OEIS|A000225}}</ref>:

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

== Свойства ==
Для всех <math>M_n</math> справедливо следующее: если <math>n</math> составное, <math>n =kl, k,l>1</math>, то и <math>M_n</math> тоже составное, что следует из разложения:

: <math>2^n - 1 = 2^{kl} - 1 = (2^k - 1)(2^{k(l-1)} + 2^{k(l-2)} + \dots + 1),</math>.

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

Любой делитель составного числа <math>M_p</math> для простого <math>p</math> имеет вид <math>2 \cdot p \cdot k + 1</math>, где <math>k</math> — [[натуральное число]] (это является следствием [[малая теорема Ферма|малой теоремы Ферма]]).

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

== Простые числа Мерсенна ==
Для всех простых чисел вида <math>2^n - 1</math> показатель степени <math>n</math> также всегда является простым числом, поэтому особо изучаются числа Мерсенна <math>M_p = 2^p - 1</math> с [[Простое число|простым]] показателем <math>p</math><ref>{{OEIS|A001348}}</ref> (в некоторых работах только такие числа считаются числами Мерсенна). Последовательность простых чисел Мерсенна начинается так<ref>{{OEIS|A000668}}</ref>:

: {{ч|3}}, {{ч|7}}, {{ч|31}}, {{ч|127}}, 8191, {{formatnum:131071}}, {{formatnum:524287}}, {{ч|2 147 483 647}}, {{s|2 305 843 009 213 693 951}}, {{s|618 970 019 642 690 137 449 562 111}}, {{s|162 259 276 829 213 363 391 578 010 288 127}}, {{ч|170 141 183 460 469 231 731 687 303 715 884 105 727}}…

Показатели <math>p</math> известных простых чисел Мерсенна образуют последовательность<ref>{{OEIS|A000043}}</ref><ref name="gimp">{{cite web|title=List of Known Mersenne Prime Numbers|url=http://www.mersenne.org/primes/|work=Great Internet Mersenne Prime Search|access-date=2016-12-09|lang=en|archive-date=2016-03-15|archive-url=https://web.archive.org/web/20160315163023/http://www.mersenne.org/primes/|url-status=live}}</ref>:

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

Числа Мерсенна получили известность в связи с эффективным [[тест простоты|алгоритмом проверки на простоту]] чисел Мерсенна — [[тест Люка — Лемера|тестом Люка — Лемера]], благодаря которому простые числа Мерсенна давно удерживают лидерство как [[Наибольшее известное простое число|самые больши́е известные простые числа]]<ref>{{cite web|title=The Largest Known Primes--A Summary|url=http://www.utm.edu/research/primes/largest.html|website=The Prime Pages|date=2018-12-26|access-date=2018-12-28|lang=en|archive-date=2008-11-22|archive-url=https://web.archive.org/web/20081122004339/http://www.utm.edu/research/primes/largest.html|url-status=live}}</ref>. Также простые числа Мерсенна применяются для построения [[ГПСЧ|генераторов псевдослучайных чисел]] с большими [[периодическая функция|периодами]]<ref>{{статья |автор=R. P. Brent, P. Zimmermann |заглавие=Random number generators with period divisible by a Mersenne prime |издание=Lecture Notes in Computer Science |том=2667 |год=2003 |страницы=1—10 |ссылка=http://wwwmaths.anu.edu.au/~brent/pub/pub211.html |archivedate=2012-03-20 |archiveurl=https://web.archive.org/web/20120320214756/http://wwwmaths.anu.edu.au/~brent/pub/pub211.html }}</ref>, таких как [[вихрь Мерсенна]]{{sfn|Matsumoto, Nishimura|2017|name="twister"}}.

== Поиск простых чисел Мерсенна ==
[[Наибольшее известное простое число|Самым больши́м известным простым числом]] ({{на|2024}}) является число Мерсенна <math>2^{136279841} - 1</math>, найденное 12 октября 2024 года Люком Дюрантом в рамках проекта [[Добровольные вычисления|добровольных вычислений]] [[GIMPS]]. [[Десятичная система счисления|Десятичная запись]] числа содержит {{число|41024320}} цифр<ref name="GIMPS-2024">{{cite web |title=GIMPS Project Discovers Largest Known Prime Number: 2<sup>136,279,841</sup>-1 |url=https://www.mersenne.org/primes/press/M136279841.html |date=2024-10-21 |work=Mersenne Research, Inc. |access-date=2024-10-21 |archive-date=2024-10-23 |archive-url=https://web.archive.org/web/20241023231222/https://www.mersenne.org/primes/press/M136279841.html |url-status=live }}</ref><ref>{{cite web |url=https://www.securitylab.ru/news/553199.php |title=GPU победил математику: найдено рекордное простое число из 41млн цифр |website=SecurityLab.ru |date=2024-10-21 |access-date=2024-10-21 |archive-date=2024-11-06 |archive-url=https://web.archive.org/web/20241106043354/https://www.securitylab.ru/news/553199.php |url-status=live }}</ref>.

Всего {{на|2024}} известно 52 простых числа Мерсенна, при этом порядковые номера достоверно установлены только у первых 48<ref>{{Cite web|url=https://www.mersenne.org/report_milestones/|title=GIMPS Milestones|website=www.mersenne.org|access-date=2022-04-05|archive-date=2021-10-13|archive-url=https://web.archive.org/web/20211013062600/https://www.mersenne.org/report_milestones/|url-status=live}}</ref> чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного. При этом 45-е простое число Мерсенна <math>M_{37156667}</math> было найдено на две недели позднее 47-го известного простого числа Мерсенна <math>M_{43112609}</math>, а 46-е известное простое число Мерсенна <math>M_{42643801}</math> было найдено только через год.

За нахождение простого числа Мерсенна <math>M_{43112609}</math> проектом [[GIMPS]] в 2009 году была получена премия в 100 тыс. [[доллар США|долларов США]], назначенная сообществом [[Electronic Frontier Foundation]] за нахождение простого числа, [[десятичная система счисления|десятичная запись]] которого содержит не менее 10 миллионов цифр<ref>[https://www.eff.org/press/archives/2009/10/14-0 Record 12-Million-Digit Prime Number Nets $100,000 Prize] {{Wayback|url=https://www.eff.org/ru/press/archives/2009/10/14-0 |date=20211226191500 }}{{ref-en}}</ref>.

== Вариации и обобщения ==
{{ЛП|Двойное число Мерсенна}}
{{ЛП|Число Каталана — Мерсенна}}
{{якорь|Двойное число Мерсенна}}'''''Двойное число Мерсенна''''' — число вида <math>M_{M_n} = 2^{2^n - 1} - 1</math>. На {{CURRENTYEAR}} год известны только 4 простых числа такого вида (при <math>n = 2, 3, 5, 7</math>).

{{якорь|Число Каталана — Мерсенна}}'''''Число Каталана — Мерсенна''''' — член последовательности чисел, начинающейся с 2 и строящейся путём применения функции <math>2^n - 1</math> к предыдущему члену <math>n</math>; первые элементы<ref>{{OEIS|id=A007013}}</ref>:
: 2, 3, 7, [[127 (число)|127]], [[170141183460469231731687303715884105727]]…
[[Каталан, Эжен Шарль|Каталан]] предполагал, что эти числа просты «вплоть до некоторого предела».

{{якорь|Обобщённое число Мерсенна}}'''''Обобщённое число Мерсенна''''' — число вида:

: <math>h^0 + h^1 + h^2 + \dots + h^{n-1} = \frac{h^n - 1}{h - 1} = M_{h,n}</math>.

Такое обобщение связано с тем, что <math>2^n - 1</math> можно представить в виде суммы <math>n</math> первых членов возрастающей [[Геометрическая прогрессия|геометрической прогрессии]]:
: <math>2^n - 1 = 2^0 + 2^1 + 2^2 + \dots + 2^{n-1} = \frac{2^n -1}{2 - 1}</math>,

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

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

Неизвестно, существуют ли простые числа Каталана — Мерсенна при <math>n > 4</math>

Неизвестно, существуют ли простые двойные числа Мерсенна при <math>n > 7</math>.

== См. также ==
* [[Наибольшее известное простое число]]
* [[GIMPS]]

== Примечания ==
{{примечания|2}}

== Ссылки ==
* {{MathWorld | title=Mersenne Prime |urlname=MersennePrime}}
* {{MathWorld | title=Mersenne Number |urlname=MersenneNumber}}
* {{MathWorld | title=Double Mersenne Numbers |urlname=DoubleMersenneNumber}}
* {{статья |автор=[[Коняев, Андрей Юрьевич|Андрей Коняев]] |ссылка=http://lenta.ru/articles/2013/02/12/mersenne/ |заглавие=Проще некуда. Найдено простое число длиной в пять романов «Война и мир» |издание=lenta.ru |год=12 февраля 2013}}
* [https://www.mersenne.org/ Проект поиска простых чисел Мерсенна (GIMPS)]{{ref-en}}.
* [http://www.doublemersennes.org/ Проект поиска делителей двойных чисел Мерсенна ММ31, ММ61, ММ89, ММ107, ММ127]{{ref-en}}.

{{DEFAULTSORT:Мерсенн}}
{{Interwiki extra|qid=Q186875}}
{{Нерабочие сноски|дата=2024-10-23}}
[[Категория:Целочисленные последовательности]]
[[Категория:Классы простых чисел]]