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

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

Числа Мерсенна Mn{displaystyle M_{n}} при n=1,2,3,…{displaystyle n=1,2,3,dots } образуют последовательность[1]:

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

Эти числа примечательны тем, что некоторые из таких чисел являются простыми при больших значениях n{displaystyle n}.

Свойства

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

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

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

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

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

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

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

3, 7, 31, 127, 8191, 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, …

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

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…

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

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

Самым больши́м известным простым числом (на июль 2018 года) является число Мерсенна M77232917=277232917−1{displaystyle M_{77232917}=2^{77232917}-1}, найденное 26 декабря 2017 года Джонатаном Пэйсом (англ. Jonathan Pace) в рамках проекта добровольных вычислений GIMPS. Десятичная запись числа M77232917{displaystyle M_{77232917}} содержит 23 249 425 цифр[7].

Всего на июнь 2018 года известно 50 простых чисел Мерсенна, при этом порядковые номера достоверно установлены только у первых 47 чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного[4]. Примечательно, что 45-е простое число Мерсенна M37156667{displaystyle M_{37156667}} было найдено на две недели позднее 47-го известного простого числа Мерсенна M43112609{displaystyle M_{43112609}}, а 46-е известное простое число Мерсенна M42643801{displaystyle M_{42643801}} было найдено только через год.

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

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

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

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

h0+h1+h2+⋯+hn−1=hn−1h−1=Mh,n{displaystyle h^{0}+h^{1}+h^{2}+dots +h^{n-1}={frac {h^{n}-1}{h-1}}=M_{h,n}}.

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

2n−1=20+21+22+⋯+2n−1=2n−12−1{displaystyle 2^{n}-1=2^{0}+2^{1}+2^{2}+dots +2^{n-1}={frac {2^{n}-1}{2-1}
}},

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

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

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

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

Примечания

  1. последовательность A000225 в OEIS
  2. последовательность A001348 в OEIS
  3. последовательность A000043 в OEIS
  4. 1 2 List of Known Mersenne Prime Numbers (неопр.). Great Internet Mersenne Prime Search. Дата обращения: 9 декабря 2016.
  5. The Largest Known Primes (англ.)
  6. R. P. Brent, P. Zimmermann. Random number generators with period divisible by a Mersenne prime // Lecture Notes in Computer Science. — 2003. — Т. 2667. — С. 1—10.
  7. GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1 (неопр.). Mersenne Research, Inc. (3 January 2018). Дата обращения: 3 января 2018.
  8. EFF Cooperative Computing Awards (англ.)

Ссылки