imported>Alex NB OT: унификация языковых шаблонов, замена устаревших имён параметров (2)

2025-11-15T11:06:48Z

унификация языковых шаблонов, замена устаревших имён параметров (2)

Новая страница

'''Число Мерсе́нна''' — число вида <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>:

: {{val|3}}, {{val|7}}, {{val|31}}, {{val|127}}, {{val|8191}}, {{val|131071}}, {{val|524287}}, {{val|2147483647}}, 2 305 843 009 213 693 951, 618 970 019 642 690 137 449 562 111, 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>:

: {{val|2}}, {{val|3}}, {{val|5}}, {{val|7}}, {{val|13}}, {{val|17}}, {{val|19}}, {{val|31}}, {{val|61}}, {{val|89}}, {{val|107}}, {{val|127}}, {{val|521}}, {{val|607}}, {{val|1279}}, {{val|2203}}, {{val|2281}}, {{val|3217}}, {{val|4253}}, {{val|4423}}, {{val|9689}}, {{val|9941}}, {{val|11213}}, {{val|19937}}, {{val|21701}}, {{val|23209}}, {{val|44497}}, {{val|86243}}, {{val|110503}}, {{val|132049}}, {{val|216091}}, {{val|756839}}, {{val|859433}}, {{val|1257787}}, {{val|1398269}}, {{val|2976221}}, {{val|3021377}}, {{val|6972593}}, {{val|13466917}}, {{val|20996011}}, {{val|24036583}}, {{val|25964951}}, {{val|30402457}}, {{val|32582657}}, {{val|37156667}}, {{val|42643801}}, {{val|43112609}}, {{val|57885161}}, {{val|74207281}}, {{val|77232917}}, {{val|82589933}}, {{val|136279841}}, …

Числа Мерсенна получили известность в связи с эффективным [[тест простоты|алгоритмом проверки на простоту]] чисел Мерсенна — [[тест Люка — Лемера|тестом Люка — Лемера]], благодаря которому простые числа Мерсенна давно удерживают лидерство как [[Наибольшее известное простое число|самые больши́е известные простые числа]]<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>. [[Двенадцатое простое число Мерсенна]] удерживало титул самого большого известного простого числа в течение 75 лет с 1876 по 1951 годы. Простые числа Мерсенна применяются для построения [[ГПСЧ|генераторов псевдослучайных чисел]] с большими [[периодическая функция|периодами]]<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 |archive-date=2012-03-20 |archive-url=https://web.archive.org/web/20120320214756/http://wwwmaths.anu.edu.au/~brent/pub/pub211.html }}</ref>, таких как [[вихрь Мерсенна]].

== Поиск простых чисел Мерсенна ==
По состоянию {{на|2025}} [[Наибольшее известное простое число|самым больши́м известным простым числом]] является число Мерсенна <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>.

Всего {{на|2025}} известно 52 простых числа Мерсенна, при этом порядковые номера достоверно установлены только у первых 50 чисел<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> было найдено только через год.

За нахождение 47-го простого числа Мерсенна <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>.

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

== Ссылки ==
* {{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}}

[[Категория:Целочисленные последовательности]]
[[Категория:Классы простых чисел]]

Число Мерсенна - История изменений

imported>Alex NB OT: унификация языковых шаблонов, замена устаревших имён параметров (2)