В течение многих столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких очевидных делителей, как 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ оказался не очень эффективен. Теперь эта погоня утихла, появились так называемые тесты простоты. Один из таких тестов - тест Люка-Лемера для чисел Мерсенна.
Простые числа Мерсенна являются простыми числами специального вида
Мр = 2^p - 1
где р — другое простое число. Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях. Свое название они получили в честь французского монаха Мерена Мерсенна (1588–1648), который много занимался проблемой совершенных чисел.
Если начать вычислять такие числа для различных простых чисел р, то видно, что не все они оказываются простыми. Например,
М2 = 2^2 — 1 = 3 = простое,
М3 = 2^3 — 1 = 7 = простое,
М5 = 2^5 — 1 = 31 = простое,
М7 = 2^7 — 1 = 127 = простое,
М11 = 2^11 — 1 = 2047 = 23*89.
Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел Мp для различных простых чисел р.
Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение. То, что с этой работой все-таки можно справиться уже для больших чисел, объясняется существованием эффективных алгоритмов.
Вычисление самого большого из известных простых чисел, числа M82589933, найденного 7 декабря 2018 года Патриком Лярошем в рамках проекта добровольных вычислений GIMPS, является довольно сложной задачей и, по-видимому, нет смысла воспроизводить здесь это число. Если же мы захотим узнать, сколько цифр содержит это число, то мы можем сделать это, не вычисляя самого числа.
Вместо нахождения количества цифр числа Мр = 2^p — 1 рассмотрим эту задачу для числа Мр + 1 = 2^р.
Эти два числа имеют одинаковое количество цифр, так как если бы число Мр + 1 имело на одну цифру больше, то оно должно было бы оканчиваться на 0. Но это невозможно ни для какой степени числа 2, что видно из ряда
2, 4, 8, 16, 32, 64, 128, 256….
в котором последняя цифра в каждом числе может быть только одним из чисел
2, 4, 8, 6.
Чтобы найти количество цифр числа 2^p, вспомним, что lg (2^p)= p lg 2.
Тогда для p = 82589933 получаем
lg (2^82589933)= 24 862 047, 172…,
и так как характеристика этого числа равна 24 862 047, то мы приходим к выводу, что число 2^p имеет 24 862 047 + 1 = 24 862 048 цифр.