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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Числа Мерсе́нна — числа вида M_n = 2^n - 1, где n — натуральное число. Названы в честь французского математика Марена Мерсенна.

Последовательность чисел Мерсенна начинается так:

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

Иногда числами Мерсенна называют числа M_p с простыми индексами p. Эта последовательность начинается так:

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)

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

Свойства[править | править вики-текст]

Простые числа Мерсенна[править | править вики-текст]

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

На сентябрь 2013 года самым больши́м известным простым числом является число Мерсенна M_{57885161} = 2^{57885161} - 1, найденное 25 января 2013 года Кертисом Купером (англ. Curtis Cooper) в рамках проекта распределённых вычислений GIMPS. Десятичная запись числа M_{57885161} содержит 17 425 170 цифр.

Всего известно 48 простых чисел Мерсенна. При этом до начала 2014 года порядковые номера были с уверенностью установлены только у первых 42 чисел[2]; 23 февраля 2014 года после произведенных перепроверок был установлено, что 43-е найденное число Мерсенна M_{30402457} действительно является 43-м членом данной последовательности[3]. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

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

M_p: 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, … (последовательность A000668 в OEIS)
p: 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, 57 885 161, … (последовательность A000043 в OEIS)

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

Вариации и обобщения[править | править вики-текст]

  • Двойные числа Мерсенна определяются как MM_n = M_{M_n} = 2^{2^n - 1} - 1. На сегодняшний день известны только четыре простых числа такого вида (при n = 2,3,5,7).

Открытые проблемы[править | править вики-текст]

  • Бесконечность количества простых чисел Мерсенна и их асимптотика.
  • Простота числа M_{M_{61}} = 2^{2^{61} - 1} - 1.

Применение[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. The Largest Known Primes (англ.)
  2. Mersenne Primes: History, Theorems and Lists (англ.)
  3. Great Internet Mersenne Prime Search (англ.)
  4. EFF Cooperative Computing Awards (англ.)
  5. R. P. Brent, P. Zimmermann Random number generators with period divisible by a Mersenne prime // Lecture Notes in Computer Science. — 2003. — Т. 2667. — С. 1-10.

Ссылки[править | править вики-текст]