Problem 21: Amicable Numbers

Mathematical Development

Definitions

Definition 1 (Divisor-Sum Functions). For $n \in \mathbb{Z}_{>0}$, the divisor-sum function is

and the restricted divisor-sum function (sum of proper divisors) is $s(n) = \sigma_1(n) - n$.

Definition 2 (Amicable Pair). An ordered pair $(a, b) \in \mathbb{Z}_{>0}^2$ with $a \neq b$ is amicable if $s(a) = b$ and $s(b) = a$.

Theorems and Proofs

Theorem 1 (Multiplicativity of $\sigma_1$). The function $\sigma_1$ is multiplicative: if $\gcd(m, n) = 1$, then $\sigma_1(mn) = \sigma_1(m)\,\sigma_1(n)$. Consequently, for $n = \prod_{i=1}^{k} p_i^{a_i}$,

Proof. Let $\gcd(m, n) = 1$. The map $(d_1, d_2) \mapsto d_1 d_2$ is a bijection from $\{d_1 : d_1 \mid m\} \times \{d_2 : d_2 \mid n\}$ to $\{d : d \mid mn\}$. (Surjectivity follows from the unique factorization in $\mathbb{Z}$ and the coprimality condition; injectivity is immediate.) Therefore

For a prime power $p^a$, the complete list of divisors is $\{1, p, p^2, \ldots, p^a\}$, so

by the closed form of the geometric series. The product formula follows by induction on the number of distinct prime factors, applying multiplicativity at each step. $\square$

Lemma 1 (Trial-Division Computation of $s(n)$). The value $s(n)$ can be computed in $O(\sqrt{n})$ arithmetic operations.

Proof. Every divisor $d$ of $n$ satisfies either $d \leq \sqrt{n}$ or $n/d \leq \sqrt{n}$ (or both, when $d = \sqrt{n}$). Hence divisors pair as $(d, n/d)$ for $d \leq \sqrt{n}$, and we may write

The correction $\epsilon(n)$ avoids double-counting the case $d = n/d$. The loop performs $\lfloor\sqrt{n}\rfloor$ iterations, each requiring $O(1)$ work (one division, one comparison), yielding $O(\sqrt{n})$ total. Then $s(n) = \sigma_1(n) - n$. $\square$

Theorem 2 (Enumeration). The complete set of amicable pairs $(a, b)$ with $a < b < 10{,}000$ is:

Proof. For each integer $n$ with $2 \leq n < 10{,}000$, compute $m = s(n)$. If $m \neq n$, $m > 0$, and $s(m) = n$, record the pair $\{\min(n,m), \max(n,m)\}$. This exhaustive, finite enumeration produces exactly the five pairs listed. (The computation is deterministic and terminates in at most $10{,}000$ evaluations of $s$.) $\square$

Editorial

We enumerate every integer $n < N$ and test the amicable condition directly. The helper $s(n)$ computes the sum of proper divisors by scanning divisor pairs up to $\sqrt{n}$, then the main loop sets $m = s(n)$ and checks whether $m \ne n$ and $s(m) = n$; if so, $n$ is added to the total. This is sufficient because the definition of an amicable number is exactly the symmetric condition being tested.

Pseudocode

Algorithm: Sum of Amicable Numbers Below a Bound
Require: An integer N ≥ 2.
Ensure: The sum of all amicable numbers less than N.
1: Initialize total ← 0.
2: For each n in {2, 3, ..., N - 1}, compute m ← s(n), where s(x) denotes the sum of the proper divisors of x.
3: If m = n, continue to the next value; otherwise compute s(m).
4: If s(m) = n, update total ← total + n.
5: Return total.

Complexity Analysis

Proposition. Algorithm SumAmicable(N) runs in $O(N\sqrt{N})$ time and $O(1)$ auxiliary space.

Proof. The outer loop iterates $N - 2$ times. Each iteration calls $s(n)$ at most twice (once for $s(n)$ and conditionally once for $s(m)$). By Lemma 1, each call to $s$ costs $O(\sqrt{N})$ in the worst case (since both $n < N$ and $m = O(N \log\log N)$ by the maximal order of $\sigma_1$, but $\sqrt{m} = O(\sqrt{N \log\log N}) = O(\sqrt{N})$ asymptotically). Thus total work is $O(N \cdot \sqrt{N}) = O(N^{3/2})$. No arrays are required beyond loop variables, so auxiliary space is $O(1)$.

Alternative. A divisor-sum sieve (iterating each $i$ and adding $i$ to $s(j)$ for all multiples $j = 2i, 3i, \ldots$) computes all values $s(n)$ for $n \leq N$ in $O(N \log N)$ time and $O(N)$ space, yielding an $O(N \log N)$ algorithm overall. $\square$

Answer

#include <bits/stdc++.h>
using namespace std;

int sum_proper_divisors(int n) {
    if (n <= 1) return 0;
    int s = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            s += i;
            if (i != n / i) s += n / i;
        }
    }
    return s;
}

int main() {
    int total = 0;
    for (int a = 2; a < 10000; a++) {
        int b = sum_proper_divisors(a);
        if (b != a && b > 0 && sum_proper_divisors(b) == a)
            total += a;
    }
    cout << total << endl;
    return 0;
}

def sum_proper_divisors(n):
    if n <= 1:
        return 0
    s = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            s += i
            if i != n // i:
                s += n // i
        i += 1
    return s

def solve():
    LIMIT = 10000
    total = 0
    for a in range(2, LIMIT):
        b = sum_proper_divisors(a)
        if b != a and b > 0 and sum_proper_divisors(b) == a:
            total += a
    print(total)