Как находят совершенные числа

Совершенные числа — это такие натуральные числа, которые равны сумме своих делителей, исключая само число. Например, 6 является совершенным, потому что его делители 1, 2 и 3, и 1+2+3=6.
Алгоритмы нахождения совершенных чисел
1. Формула Эйлера: Совершенные числа могут быть найдены через формулу Эйлера: P=2p−1×(2p−1) где 2p−1 — это простое число (называемое числом Мерсенна). Это означает, что для поиска совершенных чисел сначала нужно найти простые числа Мерсенна.
2. Поиск простых чисел Мерсенна:
o Используются различные алгоритмы для нахождения простых чисел, среди которых:
 Сито Эратосфена: эффективный метод для нахождения всех простых чисел до заданного числа.
 Тест Миллера-Рабина: вероятностный тест для проверки простоты больших чисел.
 Тест Люка-Лемера: специализированный тест, используемый для проверки простоты чисел Мерсенна.
3. Системы вычислений:
o Современные вычислительные системы, такие как GIMPS (Great Internet Mersenne Prime Search), используют распределенные вычисления для поиска больших простых чисел Мерсенна и, следовательно, совершенных чисел. Участники GIMPS используют свои компьютеры для выполнения тестов на простоту, что позволяет находить новые большие совершенные числа.
4. Алгоритмы для проверки совершенности:
o Проверка, является ли число совершенным, может быть выполнена с помощью простого перебора делителей. Однако для больших чисел это может быть неэффективным, и поэтому используются более оптимизированные методы на основе свойств делителей.
Пример нахождения совершенного числа
1. Найдем простое число Мерсенна для p=5:25−1=31(простое число)
2. Подставим p в формулу Эйлера:P=25−1×(25−1)=24×31=16×31=496
Таким образом, 496 является совершенным числом.
Заключение
Современные алгоритмы находят совершенные числа, используя комбинацию теоретических результатов (таких как формула Эйлера) и мощных вычислительных методов для поиска простых чисел. Благодаря этому были обнаружены очень большие совершенные числа, которые невозможно было бы найти вручную.