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 for checking the primality of numbers, Printf for formatted output
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) # We start with p^0 = 1
pcon = one(p) # Initializing the sum with the value 1 (p^0)
for i in 1:a # For each degree from 1 to a
n *= p # Increasing the power of p: p^i
pcon += n # Add p^i to the sum
end
return pcon # We return the amount: 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) # The initial value of the product is 1
for (p, a) in factor(n) # For each prime factor p of degree a in the expansion of n
dsum *= pcontrib(p, a) # Multiply by the sum (1 + p + p^2 + ... + p^a)
end
dsum -= n # We subtract the number itself to get the sum of only its own divisors.
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) # Search for pairs up to L value (default is 20 million)
acnt = 0 # Counter of found pairs
# Information message output
println("Amicable pairs not greater than ", L)
# We iterate over all the numbers from 2 to L
for i in 2:L
!isprime(i) || continue # Skip the primes (they have the sum of their own divisors always 1)
j = divisorsum(i) # Calculate the sum of the proper divisors of the number i
# Checking the friendliness condition:
# - j must be less than i (to avoid repetition)
# - the sum of the proper divisors of j must be equal to i
j < i && divisorsum(j) == i || continue
# If a pair is found, we increment the counter and output the result.
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() # Starting the search with default parameters (up to 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