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

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

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, .....

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

Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. На данный момент самым большим известным простым числом является число Мерсенна M_43112609 = 2^43112609 − 1, найденное в августе 2008 года в рамках проекта распределённых вычислений GIMPS. Длина M_43112609 составляет 12978189 десятичных цифр, что позволило GIMPS в 2009 году получить премию в 100000 долларов США, назначенную сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.

Всего известно 47 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 40. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

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

M_p: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, ..... p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, .....

Применение

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