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

Числа Мерсенна  — числа вида Mn=2n1, где n —натуральное число. Эти числа примечательны тем, что некоторые из нихявляются простыми. Названы в честь французского математика МаренаМерсенна, исследовавшего их свойства в XVII веке.

Определения


Числа Мерсенна в широком смысле — числа вида Mn=2n1,где n — натуральное число.
 Числа Мерсенна Mn при n=1,2,3, образуют последовательность:

 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16 383, 32767, , 131 071, \ldots
 Иногда числами Мерсенна называют только числа видаMp=2p1 с простым показателем p. Эта последовательностьначинается так:

 3, 7, 31, 127, 2047, 8191, 131 071, 524 287, 8 388 607, 536 870 911, ,137 438 953 471, \ldots
Простое число Мерсенна  — простое число видаMn=2n1, где n — натуральное число, то есть числаМерсенна, являющиеся простыми. Для всех простых чисел вида 2n1показатель степени n также всегда является простым числом, поэтомупростые числа Мерсенна корректно определены вне зависимости отвыбранного определения чисел Мерсенна. Простые числа Мерсенна образуютпоследовательность:

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

 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203,2281, 3217, 4253, 4423, 9689, 9941, , , , , , , , , , , , , , , , , , ,, , , , , \ldots .

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



  • Для всех Mn справедливо, если n составное, то и Mn тоже составное, что следует из:

2n1=2kl1=(2k1)(2k(l1)+2k(l2)++1),

 где kl=n.
 Отсюда сразу следует: если Mn является простым, то число n такжепростое. Обратное утверждение в общем случае неверно, наименьшимконтрпримером является M11=2047=2389.

  • Любой делитель числа Mp для простого p имеет вид 2pk+1, где k — натуральное число (это является следствием малой теоремы Ферма).
  • Каждое чётное совершенное число имеет вид Mp(Mp+1)2=2p1(2p1), где число Мерсенна Mp является простым (это утверждение доказано Эйлером).

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


 Числа Мерсенна получили известность в связи с эффективным тестомпростоты больших чисел — тестом Люка — Лемера. Поэтому простые числаМерсенна давно удерживают лидерство как самые большие известные простыечисла.
 Самым большим известным простым числом (на декабрь 2016) является числоМерсенна M74207281=2742072811, найденное 7 января 2016 годаКертисом Купером в рамках проекта распределённых вычислений GIMPS.Десятичная запись числа M74207281 содержит цифр.
 всего известно 49 простых чисел Мерсенна. При этом порядковые номерадостоверно установлены только у первых 45 чисел. В частности,неизвестно, существуют ли другие простые числа Мерсенна, меньшиеизвестного рекордного.
 Интересно отметить, что 45-е простое число Мерсенна M37156667 былонайдено на две недели позднее 47-го известного простого числа МерсеннаM43112609, а 46-е известное простое число Мерсенна M42643801было найдено только через год.
 За нахождение простого числа Мерсенна M43112609 проектом GIMPS в2009 году была вручена премия в 100 000 долларов США, назначеннаясообществом Electronic Frontier Foundation за нахождение простого числа,десятичная запись которого содержит не менее 10 миллионов цифр.

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



  • Двойные числа Мерсенна определяются как MMn=22n11. известны только 4 простых числа такого вида (при n = 2, 3, 5, 7).
  • Обобщённые числа Мерсенна. Так как число 2n1 можно представить в виде суммы n первых членов возрастающей геометрической прогрессии:

2n1=20+21+22++2n1=2n121,

 возможно определить обобщённые числа Мерсенна:
h0+h1+h2++hn1=hn1h1=Mh,n.

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

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



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

Применение


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