Дружественные числа
maximsidorovАлгоритм определения дружественных чисел (Amicable pairs)
Рассматриваем реализацию алгоритма поиска пар дружественных чисел до заданного предела.
Введение
Что такое дружественные числа?
Дружественные числа - это два натуральных числа, таких, что сумма собственных делителей одного числа равна другому числу, и наоборот. Например, пара является дружественной:
- Сумма собственных делителей
- Сумма собственных делителей
Разработаем алгоритм, который находит все такие пары до указанного предела.
Основная часть
Перед использованием внешнего пакета, его нужно установить:
import Pkg; Pkg.add("Primes")
Подключение необходимых библиотек:
using Primes, Printf # Primes для проверки простоты чисел, Printf для форматированного вывода
Функция расчета вклада простого множителя
Эта функция вычисляет сумму степеней простого числа от степени до .
function pcontrib(p::Int64, a::Int64)
n = one(p) # Начинаем с p^0 = 1
pcon = one(p) # Инициализация суммы значением 1 (p^0)
for i in 1:a # Для каждой степени от 1 до a
n *= p # Увеличиваем степень p: p^i
pcon += n # Добавляем p^i к сумме
end
return pcon # Возвращаем сумму: 1 + p + p^2 + ... + p^a
end
Пояснение к работе функции pcontrib:
Для вычисления суммы всех делителей числа необходимо учитывать, что если число имеет каноническое разложение , то сумма всех его делителей будет равна произведению:
Функция pcontrib вычисляет одну такую скобку для конкретного простого множителя.
Функция вычисления суммы всех делителей
Вычисляет сумму всех делителей числа, используя его разложение на простые множители.
function divisorsum(n::Int64)
dsum = one(n) # Начальное значение произведения - 1
for (p, a) in factor(n) # Для каждого простого множителя p степени a в разложении n
dsum *= pcontrib(p, a) # Домножаем на сумму (1 + p + p^2 + ... + p^a)
end
dsum -= n # Вычитаем само число, чтобы получить сумму только собственных делителей
end
Пояснение к функции divisorsum:
Используется основная теорема арифметики - каждое натуральное число можно представить как произведение степеней простых чисел (каноническое разложение). Сумма всех делителей вычисляется через произведение коэффициентов pcontrib. Затем из этой суммы вычитается само число , чтобы получить сумму ТОЛЬКО собственных делителей (меньших самого числа).
Основная функция поиска дружественных пар
Основная функция, которая осуществляет поиск всех пар дружественных чисел до лимита.
function amicables(L = 2*10^7) # Поиск пар до значения L (по умолчанию 20 миллионов)
acnt = 0 # Счетчик найденных пар
# Вывод информационного сообщения
println("Amicable pairs not greater than ", L)
# Перебираем все числа от 2 до L
for i in 2:L
!isprime(i) || continue # Пропускаем простые числа (у них сумма собственных делителей всегда 1)
j = divisorsum(i) # Вычисляем сумму собственных делителей числа i
# Проверяем условие дружественности:
# - j должен быть меньше i (чтобы не повторяться)
# - сумма собственных делителей j должна быть равна i
j < i && divisorsum(j) == i || continue
# Если пара найдена, увеличиваем счетчик и выводим результат
acnt += 1
println(@sprintf("%4d", acnt), " => ", j, ", ", i)
end
end
Пояснение к оптимизации в функции amicables:
Цикл проходит от до по возрастанию.
Проверка гарантирует, что каждая пара находится только один раз - т.е., если ранее уже встречалась пара , то она больше не будет выведена как . Также пропускаются простые числа, так как у простого числа сумма собственных делителей равна , а никогда не может образовать дружественной пары.
amicables() # Запуск поиска с параметрами по умолчанию (до 20,000,000)
Результат работы программы будет содержать список пар дружественных чисел в порядке возрастания, где первое число меньше второго.
Формат вывода: <порядковый_номер> => <меньшее_число>, <большее_число>
Заключение
Мы рассмотрели реализацию алгоритма поиска дружественных чисел на языке программирования Julia.
Алгоритм использует математические свойства разложения чисел на простые множители для эффективного вычисления суммы собственных делителей. Эффективность достигается за счет использования теории чисел вместо прямого перебора всех делителей. Программа находит все дружественные пары до заданного предела и выводит их с нумерацией. Такой подход имеет практическое применение в теории чисел и занимательной математике. Интересно отметить, что дружественные числа были известны еще древним грекам, а самая маленькая пара (220, 284) была найдена еще Пифагором.
Пример разработан с использованием материалов Rosetta Code