Algorithmic Exploration for Identifying
Friend Numbers
Introduction
This document describes an algorithm to find pairs of 'friend numbers' within the range up
to n. Friend numbers are pairs where the sum of the proper divisors of each equals the
other number. The implementation employs a modified Sieve of Eratosthenes, efficiently
calculating the sum of divisors for numbers up to n.
Algorithm Implementation and Mathematical Steps
Initialization
The algorithm begins with the initialization of the Solution class, taking n as the range limit
and a as an array to track the number of friend pairs and computational steps. An array _a is
also initialized to store the sum of divisors for each number up to n, initially filled with
zeros.
Computing Sum of Divisors
The _compute_all_sum_of_factors() method calculates the sum of proper divisors for each
number up to n using a nested loop structure. Mathematically, for each number i, this
method iterates over its multiples j = 2i, 3i, ..., mi (where mi ≤ n) and updates the sum of
divisors for j by adding i:
For each i, for each multiple j: sum_divisors[j] += i
This approach mirrors the Sieve of Eratosthenes but accumulates divisor sums instead of
identifying primes.
Identifying Friend Pairs
The _alg() method scans through the _a array to find friend pairs. For each index i, it seeks a
corresponding index j = _a[i] such that j > i and _a[j] == i, indicating a pair of friend numbers.
The algorithm uses the mathematical condition for friend numbers:
If sum_divisors[a] = b and sum_divisors[b] = a where a ≠ b, then (a, b) are friends.
This is implemented by checking if _a[_a[i]] == i for each i, confirming the bidirectional sum
of divisors condition for friend numbers.
Mathematical Steps
The sum of divisors for each number is calculated based on the principle that every divisor
of a number contributes to the sum of divisors of its multiples. This is mathematically
represented as summing over all divisors d of each number n, excluding n itself, to get the
sum of proper divisors σ(n) = Σ d | n, d < n.
This efficient accumulation of divisor sums significantly reduces the computational
complexity compared to a brute-force approach of individually calculating the sum of
divisors for each number.
Time Complexity Calculation
The time complexity of the algorithm is largely determined by the nested loop structure in
the divisor summation process. The outer loop runs n times, and for each i, the inner loop
updates the sum of divisors for multiples of i, effectively performing ∑(n/i) operations over
all i, which approximates to n log n due to the harmonic series.
This results in an overall time complexity of O(n log n), making the algorithm efficient for
large values of n and suitable for practical applications.