Найдено простое число длиной в семь романов «Война и мир»

Визуализация простых и составных чисел. Окружности имеют целый диаметр n и отмечают числа n, 2n, 3n и так далее.

Иллюстрация: sievesofchaos.com

Математик Кертис Купер нашел 49-е простое число Мерсенна. Это самое большое из известных на настоящий момент простых чисел.

Числами Мерсенна называются числа вида 2p — 1. Среди них встречаются как простые так и составные числа. Показатель p для найденного Купером числа составляет 74 207 281. Десятичная запись числа содержит 22 338 618 знаков. Для сравнения, в «Войне и мире» Толстого примерно 3,1 миллиона знаков.

Для Купера это не первый рекорд: в 2013 году он открыл 48-е простое число Мерсенна, длина десятичной записи которого составила около 17 миллионов знаков.

Открытие было сделано в рамках проекта распределенных вычислений GIMPS (Great Internet Mersenne Prime Search). Это первый в истории исследовательский проект распределенных вычислений. Он был запущен в 1995 году и изначально был рассчитан на работу с 386-ми процессорами. Сейчас программу, работающую под всеми основными операционными системами, может установить себе любой желающий. Суммарная вычислительная мощность проекта к концу 2012 года составляла уже 95 терафлопс.

Для работы программа использует тест Люка-Лемера. Суть его заключается в следующем: для фиксированного числа Мерсенна вычисляется некоторая рекуррентная последовательность. Число Мерсенна с показателем p просто тогда и только тогда, когда p — 2 член последовательности делится на это число. Сложность работы алгоритма составляет порядка третьей степени log n, где n — само число Мерсенна.

Андрей Коняев

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.