Русская Википедия:Число Мерсенна
Число Мерсе́нна — число вида <math>M_n = 2^n - 1</math>, где <math>n</math> — натуральное число; такие числа примечательны тем, что некоторые из них являются простыми при больших значениях <math>n</math>. Названы в честь французского математика Маре́на Мерсенна, исследовавшего их свойства в XVII веке.
Первые числа Мерсенна[1]:
- 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>[2] (в некоторых работах только такие числа считаются числами Мерсенна). Последовательность простых чисел Мерсенна начинается так[3]:
- Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, 8191, 131 071, 524 287, Шаблон:Ч, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:Ч…
Показатели <math>p</math> известных простых чисел Мерсенна образуют последовательность[4][5]:
- 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S, Шаблон:S…
Числа Мерсенна получили известность в связи с эффективным алгоритмом проверки на простоту чисел Мерсенна — тестом Люка — Лемера. Поэтому простые числа Мерсенна давно удерживают лидерство как самые больши́е известные простые числа[6]. Также простые числа Мерсенна применяются для построения генераторов псевдослучайных чисел с большими периодами[7], таких как вихрь Мерсенна.
Поиск простых чисел Мерсенна
Самым больши́м известным простым числом (Шаблон:На) является число Мерсенна <math>M_{82589933} = 2^{82589933} - 1</math>, найденное 7 декабря 2018 года Патриком Лярошем в рамках проекта добровольных вычислений GIMPS. Десятичная запись числа <math>M_{82589933}</math> содержит 24 862 048 цифр[8].
Всего Шаблон:На известно 51 простое число Мерсенна, при этом порядковые номера достоверно установлены только у первых 48[9] чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного. Примечательно, что 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 миллионов цифр[10].
Вариации и обобщения
Шаблон:ЛП Шаблон:ЛП Двойное число Мерсенна — число вида <math>M_{M_n} = 2^{2^n - 1} - 1</math>. Шаблон:На известны только 4 простых числа такого вида (при <math>n = 2, 3, 5, 7</math>).
Число Каталана — Мерсенна — член последовательности чисел, начинающейся с 2 и строящейся путём применения функции <math>2^n - 1</math> к предыдущему члену <math>n</math>; первые элементы[11]:
- 2, 3, 7, 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
- Шаблон:MathWorld
- Шаблон:MathWorld
- Шаблон:Статья
- Проект поиска простых чисел Мерсенна (GIMPS)Шаблон:Ref-en.
- Проект поиска делителей двойных чисел Мерсенна ММ31, ММ61, ММ89, ММ107, ММ127Шаблон:Ref-en.
