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

Чи́сла Мерсе́нна (англ. Mersenne numbers) — числа вида <math>M_n = 2^n - 1</math>, где <math>n</math> — натуральное число. Эти числа примечательны тем, что некоторые из них являются простыми. Названы в честь французского математика Маре́на Мерсенна, исследовавшего их свойства в XVII веке.

Определения

Числа Мерсенна в широком смысле — числа вида <math>M_n = 2^n - 1</math>, где <math>n</math> — натуральное число.

Числа Мерсенна <math>M_n</math> при <math>n=1,2,3,\dots</math> образуют последовательность:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16 383, 32 767, 65 535, 131 071, … (последовательность A000225 в OEIS)

Иногда числами Мерсенна называют только числа вида <math>M_p = 2^p - 1</math> с простым показателем <math>p</math>. Эта последовательность начинается так:

3, 7, 31, 127, 2047, 8191, 131 071, 524 287, 8 388 607, 536 870 911, 2 147 483 647, 137 438 953 471, … (последовательность A001348 в OEIS)

Простое число Мерсе́нна (англ. Mersenne prime) — простое число вида <math>M_n = 2^n - 1</math>, где n — натуральное число, то есть числа Мерсенна, являющиеся простыми. Для всех простых чисел вида <math>2^n - 1</math> показатель степени <math>n</math> также всегда является простым числом, поэтому простые числа Мерсенна корректно определены вне зависимости от выбранного определения чисел Мерсенна.

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

3, 7, 31, 127, 8 191, 131 071, 524 287, 2 147 483 647, 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, … (последовательность A000668 в OEIS)

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

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, … (последовательность A000043 в OEIS)

Свойства чисел Мерсенна

• Для всех <math>M_n</math> справедливо, если <math>n</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>k \cdot l = n.</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>M_{74207281} = 2^{74207281} - 1</math>, найденное 7 января 2016 года Кертисом Купером (англ. Curtis Cooper) в рамках проекта распределённых вычислений GIMPS. Десятичная запись числа <math>M_{74207281}</math> содержит 22 338 618 цифр.

Всего известно 49 простых чисел Мерсенна. При этом на январь 2016 года порядковые номера достоверно установлены только у первых 44 чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного.

Интересно отметить, что 45-е известное (согласно нумерации на январь 2016 года) простое число Мерсенна <math>M_{37156667}</math> было найдено на две недели позднее 47-го известного простого числа Мерсенна <math>M_{43112609}</math>, а 46-е известное простое число Мерсенна <math>M_{42643801}</math> было найдено только через год.

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

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

• Двойные числа Мерсенна определяются как <math>M_{M_n} = 2^{2^n - 1} - 1</math>. На январь 2016 года известны только 4 простых числа такого вида (при n = 2,3,5,7).
• Обобщённые числа Мерсенна. Так как число <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^0 + h^1 + h^2 + \dots + h^{n-1} = \frac{h^n - 1}{h - 1} = M_{h,n}.</math>

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

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

• Неизвестно, конечно или бесконечно множество простых чисел Мерсенна и плотность их распределения во множестве натуральных чисел.
• Неизвестно, является ли число <math>M_{M_{61}} = 2^{2^{61} - 1} - 1</math> простым.

Применение

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

См. также

• Числа Ферма

Ссылки

• Weisstein, Eric W. [mathworld.wolfram.com/MersennePrime.html Mersenne Prime] (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. [mathworld.wolfram.com/MersenneNumber.html Mersenne Number] (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. [mathworld.wolfram.com/DoubleMersenneNumber.html Double Mersenne Numbers] (англ.) на сайте Wolfram MathWorld.
• Андрей Коняев [lenta.ru/articles/2013/02/12/mersenne/ Проще некуда. Найдено простое число длиной в пять романов «Война и мир»] // lenta.ru. — 12 февраля 2013.

Отрывок, характеризующий Числа Мерсенна

– Пехоту низом пошлем – болотами, – продолжал Денисов, – они подлезут к саду; вы заедете с казаками оттуда, – Денисов указал на лес за деревней, – а я отсюда, с своими гусаг'ами. И по выстг'елу…
– Лощиной нельзя будет – трясина, – сказал эсаул. – Коней увязишь, надо объезжать полевее…
В то время как они вполголоса говорили таким образом, внизу, в лощине от пруда, щелкнул один выстрел, забелелся дымок, другой и послышался дружный, как будто веселый крик сотен голосов французов, бывших на полугоре. В первую минуту и Денисов и эсаул подались назад. Они были так близко, что им показалось, что они были причиной этих выстрелов и криков. Но выстрелы и крики не относились к ним. Низом, по болотам, бежал человек в чем то красном. Очевидно, по нем стреляли и на него кричали французы.
– Ведь это Тихон наш, – сказал эсаул.
– Он! он и есть!
– Эка шельма, – сказал Денисов.
– Уйдет! – щуря глаза, сказал эсаул.
Человек, которого они называли Тихоном, подбежав к речке, бултыхнулся в нее так, что брызги полетели, и, скрывшись на мгновенье, весь черный от воды, выбрался на четвереньках и побежал дальше. Французы, бежавшие за ним, остановились.
– Ну ловок, – сказал эсаул.
– Экая бестия! – с тем же выражением досады проговорил Денисов. – И что он делал до сих пор?
– Это кто? – спросил Петя.
– Это наш пластун. Я его посылал языка взять.
– Ах, да, – сказал Петя с первого слова Денисова, кивая головой, как будто он все понял, хотя он решительно не понял ни одного слова.
Тихон Щербатый был один из самых нужных людей в партии. Он был мужик из Покровского под Гжатью. Когда, при начале своих действий, Денисов пришел в Покровское и, как всегда, призвав старосту, спросил о том, что им известно про французов, староста отвечал, как отвечали и все старосты, как бы защищаясь, что они ничего знать не знают, ведать не ведают. Но когда Денисов объяснил им, что его цель бить французов, и когда он спросил, не забредали ли к ним французы, то староста сказал, что мародеры бывали точно, но что у них в деревне только один Тишка Щербатый занимался этими делами. Денисов велел позвать к себе Тихона и, похвалив его за его деятельность, сказал при старосте несколько слов о той верности царю и отечеству и ненависти к французам, которую должны блюсти сыны отечества.
– Мы французам худого не делаем, – сказал Тихон, видимо оробев при этих словах Денисова. – Мы только так, значит, по охоте баловались с ребятами. Миродеров точно десятка два побили, а то мы худого не делали… – На другой день, когда Денисов, совершенно забыв про этого мужика, вышел из Покровского, ему доложили, что Тихон пристал к партии и просился, чтобы его при ней оставили. Денисов велел оставить его.
Тихон, сначала исправлявший черную работу раскладки костров, доставления воды, обдирания лошадей и т. п., скоро оказал большую охоту и способность к партизанской войне. Он по ночам уходил на добычу и всякий раз приносил с собой платье и оружие французское, а когда ему приказывали, то приводил и пленных. Денисов отставил Тихона от работ, стал брать его с собою в разъезды и зачислил в казаки.
Тихон не любил ездить верхом и всегда ходил пешком, никогда не отставая от кавалерии. Оружие его составляли мушкетон, который он носил больше для смеха, пика и топор, которым он владел, как волк владеет зубами, одинаково легко выбирая ими блох из шерсти и перекусывая толстые кости. Тихон одинаково верно, со всего размаха, раскалывал топором бревна и, взяв топор за обух, выстрагивал им тонкие колышки и вырезывал ложки. В партии Денисова Тихон занимал свое особенное, исключительное место. Когда надо было сделать что нибудь особенно трудное и гадкое – выворотить плечом в грязи повозку, за хвост вытащить из болота лошадь, ободрать ее, залезть в самую середину французов, пройти в день по пятьдесят верст, – все указывали, посмеиваясь, на Тихона.
– Что ему, черту, делается, меренина здоровенный, – говорили про него.
Один раз француз, которого брал Тихон, выстрелил в него из пистолета и попал ему в мякоть спины. Рана эта, от которой Тихон лечился только водкой, внутренне и наружно, была предметом самых веселых шуток во всем отряде и шуток, которым охотно поддавался Тихон.
– Что, брат, не будешь? Али скрючило? – смеялись ему казаки, и Тихон, нарочно скорчившись и делая рожи, притворяясь, что он сердится, самыми смешными ругательствами бранил французов. Случай этот имел на Тихона только то влияние, что после своей раны он редко приводил пленных.
Тихон был самый полезный и храбрый человек в партии. Никто больше его не открыл случаев нападения, никто больше его не побрал и не побил французов; и вследствие этого он был шут всех казаков, гусаров и сам охотно поддавался этому чину. Теперь Тихон был послан Денисовым, в ночь еще, в Шамшево для того, чтобы взять языка. Но, или потому, что он не удовлетворился одним французом, или потому, что он проспал ночь, он днем залез в кусты, в самую середину французов и, как видел с горы Денисов, был открыт ими.


Поговорив еще несколько времени с эсаулом о завтрашнем нападении, которое теперь, глядя на близость французов, Денисов, казалось, окончательно решил, он повернул лошадь и поехал назад.
– Ну, бг'ат, тепег'ь поедем обсушимся, – сказал он Пете.
Подъезжая к лесной караулке, Денисов остановился, вглядываясь в лес. По лесу, между деревьев, большими легкими шагами шел на длинных ногах, с длинными мотающимися руками, человек в куртке, лаптях и казанской шляпе, с ружьем через плечо и топором за поясом. Увидав Денисова, человек этот поспешно швырнул что то в куст и, сняв с отвисшими полями мокрую шляпу, подошел к начальнику. Это был Тихон. Изрытое оспой и морщинами лицо его с маленькими узкими глазами сияло самодовольным весельем. Он, высоко подняв голову и как будто удерживаясь от смеха, уставился на Денисова.