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, \ldots, mi \) (where \( mi \leq n \)) and
updates the sum of divisors for \( j \) by adding \( i \):
\[ \text{For each } i, \text{ for each multiple } j: \sigma(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:
\[ \text{If } \sigma(a) = b \text{ and } \sigma(b) = a \text{ where } a \neq b, \text{ then } (a,
b) \text{ 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.
Utility Methods
- `_increment_steps()`: Records each computational step, reflecting the algorithm's
complexity.
- `_increment_number_of_friends()`: Counts the number of friend pairs found.
- `_find_friends(i)`: Determines if the number at index \( i \) has a friend by applying the
friend number condition, returning the friend number or 0.
Computational Efficiency
The algorithm's efficiency stems from its systematic approach to computing divisor sums
and identifying friend pairs. By updating the sums for all multiples of \( i \) within the inner
loop, the algorithm ensures that each divisor contributes to the appropriate sums in a
manner akin to the Sieve of Eratosthenes, leading to a time complexity of approximately \
( O(n \log n) \) due to the nature of divisor summation.
Conclusion
The described algorithm efficiently identifies friend numbers within a specified range by
combining a modified Sieve of Eratosthenes with a logical verification of the friend number
condition. This approach balances computational efficiency with mathematical rigor,
making it effective for ranges extending to large values of \( n \).