Числа Мерсенна
Числа Мерсе́нна — числа вида Mn = 2n − 1, где n — натуральное число. Названы в честь французского математика Марена Мерсенна.
Последовательность чисел Мерсенна начинается так:
Иногда числами Мерсенна называют числа Mp с простыми индексами p. Эта последовательность начинается так:
- 3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, … (последовательность A001348 в OEIS)
Содержание |
[править] Свойства
- Если Mn является простым, то число n также простое.
- Любой делитель числа Mp для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
- Каждое чётное совершенное число имеет вид Mp(Mp + 1) / 2 = 2p − 1(2p − 1), где число Мерсенна Mp является простым (доказано Эйлером).
[править] Простые числа Мерсенна
Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые больши́е известные простые числа.[1] На данный момент самым больши́м известным простым числом является число Мерсенна M43112609 = 243112609 − 1, найденное в августе 2008 года в рамках проекта распределённых вычислений GIMPS. Длина M43112609 составляет 12978189 десятичных цифр, что позволило GIMPS в 2009 году получить премию в 100000 долларов США, назначенную сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.[2]
Всего известно 47 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 40.[3] Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.
Последовательность простых чисел Мерсенна и их показателей начинается так:
- Mp: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, … (последовательность A000668 в OEIS)
- p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, … (последовательность A000043 в OEIS)
[править] Вариации и обобщения
- Двойные числа Мерсенна определяются как
.
[править] Открытые проблемы
- Бесконечность количества простых чисел Мерсенна и их асимптотика.
- Простота числа
.
[править] Применение
На практике простые числа Мерсенна применяются для построения генераторов псевдо-случайных чисел с большими периодами[4], таких, как вихрь Мерсенна.
[править] Примечания
- ↑ The Largest Known Primes (англ.)
- ↑ EFF Cooperative Computing Awards (англ.)
- ↑ Mersenne Primes: History, Theorems and Lists (англ.)
- ↑ R. P. Brent, P. Zimmermann Random number generators with period divisible by a Mersenne prime // Lecture Notes in Computer Science. — 2003. — Т. 2667. — С. 1-10.
[править] Ссылки
- Weisstein, Eric W. Mersenne Number (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. Double Mersenne Numbers (англ.) на сайте Wolfram MathWorld.
.
.