The algorithm for determining friendly numbers (Amicable pairs)
We are considering the implementation of an algorithm for searching for pairs of friendly numbers up to a given limit.
Introduction
What are friendly numbers?
Friendly numbers are two natural numbers such that the sum of the proper divisors of one number is equal to the other number, and vice versa. For example, a couple It is friendly:
\ is the sum of its own divisors
\ is the sum of its own divisors
Let's develop an algorithm that finds all such pairs up to the specified limit.
The main part
Before using an external package, you need to install it.:
import Pkg; Pkg.add("Primes")
Connecting the necessary libraries:
using Primes, Printf # Primes для проверки простоты чисел, Printf для форматированного вывода
The function of calculating the contribution of a prime multiplier
This function calculates the sum of the powers of a prime number. from the degree before .
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
Explanation of the function operation pcontrib:
To calculate the sum of all the divisors of a number, it must be taken into account that if the number has a canonical decomposition , then the sum of all its divisors will be equal to the product:
Function pcontrib calculates one such bracket for a specific prime factor.
The function of calculating the sum of all divisors
Calculates the sum of all the divisors of a number using its prime factorization.
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
Explanation of the function divisorsum:
The basic theorem of arithmetic is used - every natural number can be represented as a product of the powers of prime numbers (canonical decomposition). The sum of all divisors is calculated through the product of the coefficients pcontrib. Then the number itself is subtracted from this amount. to get the sum of ONLY its own divisors (smaller than the number itself).
The main function of finding friendly couples
The main function that searches for all pairs of friendly numbers up to the limit.
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
Explanation of optimization in the function amicables:
The cycle runs from before in ascending order.
Check ensures that each pair is found only once, i.e. if a pair has already met before. then it will no longer be output as . Primes are also skipped, since the sum of the proper divisors of a prime number is , and can never form a friendly pair.
amicables() # Запуск поиска с параметрами по умолчанию (до 20,000,000)
The result of the program will contain a list of pairs of friendly numbers in ascending order, where the first number is less than the second.
Output format: <порядковый_номер> => <меньшее_число>, <большее_число>
Conclusion
We have reviewed the implementation of the friendly number search algorithm in the Julia programming language.
The algorithm uses the mathematical properties of decomposing numbers into prime factors to efficiently calculate the sum of their own divisors. Efficiency is achieved by using number theory instead of going through all the divisors directly. The program finds all friendly pairs up to a set limit and outputs them with numbering. This approach has practical applications in number theory and entertaining mathematics. It is interesting to note that friendly numbers were known to the ancient Greeks, and the smallest pair (220, 284) was found by Pythagoras.
The example was developed using materials from Rosetta Code