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

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

Чи́сла Мерсе́нна (англ. Mersenne numbers) — числа вида , где  — натуральное число. Эти числа примечательны тем, что некоторые из них являются простыми. Названы в честь французского математика Маре́на Мерсенна, исследовавшего их свойства в XVII веке.

Определения[править | править вики-текст]

Числа Мерсенна в широком смысле — числа вида , где  — натуральное число.

Числа Мерсенна при образуют последовательность:

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

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

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)

Простое число Мерсе́нна (англ. Mersenne prime) — простое число вида , где n — натуральное число, то есть числа Мерсенна, являющиеся простыми. Для всех простых чисел вида показатель степени также всегда является простым числом, поэтому простые числа Мерсенна корректно определены вне зависимости от выбранного определения чисел Мерсенна. Простые числа Мерсенна образуют последовательность:

3, 7, 31, 127, 8 191, 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)

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

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 , 74 207 281, … (последовательность A000043 в OEIS).

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

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

где

Отсюда сразу следует: если является простым, то число также простое. Обратное утверждение в общем случае неверно, наименьшим контрпримером является .

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

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

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

Самым больши́м известным простым числом (на декабрь 2016) является число Мерсенна , найденное 7 января 2016 года Кертисом Купером (англ. Curtis Cooper) в рамках проекта распределённых вычислений GIMPS. Десятичная запись числа содержит 22 338 618 цифр.

Всего известно 49 простых чисел Мерсенна. При этом на сентябрь 2016 года порядковые номера достоверно установлены только у первых 45 чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного[2].

Интересно отметить, что 45-е простое число Мерсенна было найдено на две недели позднее 47-го известного простого числа Мерсенна , а 46-е известное простое число Мерсенна было найдено только через год.

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

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

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

возможно определить обобщённые числа Мерсенна:

При некоторых значениях обобщённые числа Мерсенна являются простыми, например, и др.

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

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

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

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

См. также[править | править вики-текст]

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

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

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