Detailed mathematical approach

Problem Summary

Let \(d(n)\) denote the sum of the proper divisors of \(n\), meaning all positive divisors strictly smaller than \(n\). Two distinct positive integers \(a\) and \(b\) form an amicable pair when

$d(a)=b,\qquad d(b)=a,\qquad a \ne b.$

The original problem asks for the sum of all amicable numbers below \(10000\). The implementations are written for a general limit \(L\): they sum every \(a \lt L\) that belongs to an amicable pair. The partner \(b=d(a)\) may lie either below or above the limit; only \(a\) itself is required to be below \(L\).

The smallest example is the pair \((220,284)\). Its importance is not just historical. It already shows the exact two-step return that the algorithm must detect.

Mathematical Approach

The solution uses two complementary descriptions of the same quantity \(d(n)\). A sieve computes every proper-divisor sum below the search limit at once, while a prime-factor formula handles the rarer case in which the partner value lies outside the precomputed range.

The function \(d(n)\)

By definition,

$d(n)=\sum_{\substack{m\mid n\\1\le m\lt n}} m=\sigma(n)-n,$

where \(\sigma(n)\) is the sum of all positive divisors of \(n\). The amicable condition is therefore exactly the statement that \(a\) and \(b\) form a 2-cycle under the map \(d\), with the extra condition \(a\ne b\) excluding perfect numbers such as \(6\) and \(28\).

Compute all values below \(L\) with one divisor sieve

Factoring every number separately would work, but it would waste the shared structure of divisor sums. The implementations instead allocate an array for all values \(0,1,\dots,L-1\) and add each possible proper divisor to all of its multiples:

$d(kq)\mathrel{+}=q \qquad \left(q=1,2,\dots,\left\lfloor\frac{L-1}{2}\right\rfloor,\ k\ge 2,\ kq\lt L\right).$

The key invariant is that after the loop has processed a divisor \(q\), every number below \(L\) has already received every proper divisor at most \(q\), and it has received each such divisor exactly once. Because the inner loop starts at \(2q\), no number ever adds itself to its own proper-divisor sum.

The total work is governed by the harmonic series:

$\sum_{q=1}^{\lfloor(L-1)/2\rfloor}\left\lfloor\frac{L-1}{q}\right\rfloor=O(L\log L).$

That is the main reason the code is efficient even though it evaluates \(d(n)\) for every \(n\) below the limit.

Why the partner sometimes has to be factored directly

After the sieve, each candidate \(a \lt L\) produces a partner \(b=d(a)\). To decide whether \(a\) is amicable, the algorithm must still verify that \(d(b)=a\). If \(b \lt L\), the answer is already stored in the sieve table. If \(b\ge L\), the mathematical test is unchanged, but the table no longer reaches that far.

The implementations therefore compute \(d(b)\) on demand from the prime factorization of \(b\). If

$b=\prod_{i=1}^{r} p_i^{e_i},$

then multiplicativity gives

$\sigma(b)=\prod_{i=1}^{r}\left(1+p_i+\cdots+p_i^{e_i}\right)=\prod_{i=1}^{r}\frac{p_i^{e_i+1}-1}{p_i-1},$

so

$d(b)=\sigma(b)-b.$

This hybrid design is the real mathematical core of the code: precompute everything that is cheap and shared, then fall back to factorization only when the return check leaves the sieve range.

The amicable test is a 2-cycle test for \(d\)

For each \(a \lt L\), the algorithm accepts \(a\) exactly when

$d(a)=b,\qquad b\gt 0,\qquad b\ne a,\qquad d(b)=a.$

So the scan is not looking for all numbers with unusually large or small divisor sums. It is specifically looking for nontrivial 2-cycles of the proper-divisor-sum map. If both members of a pair lie below \(L\), they will both be counted, once each, when the scan reaches them.

This also explains the checkpoint at \(L=300\): the only amicable pair below 300 is \((220,284)\), so the correct partial sum is

$220+284=504.$

Worked example: \(220\) and \(284\)

The proper divisors of \(220\) are

$1,2,4,5,10,11,20,22,44,55,110,$

hence

$d(220)=1+2+4+5+10+11+20+22+44+55+110=284.$

The proper divisors of \(284\) are

$1,2,4,71,142,$

so

$d(284)=1+2+4+71+142=220.$

The same result appears from the factorization formula. Since \(220=2^2\cdot 5\cdot 11\),

$\sigma(220)=(1+2+2^2)(1+5)(1+11)=7\cdot 6\cdot 12=504,$

and therefore \(d(220)=504-220=284\). The implementations use exactly these identities, just at scale.

How the Code Works

Phase 1: build the divisor-sum table

The C++, Python, and Java implementations first allocate an array of length \(L\) filled with zeros. They then run the divisor sieve so that each entry for \(n \lt L\) becomes the exact value of \(d(n)\).

Phase 2: scan candidates and verify the partner

The implementations iterate through \(a=2,3,\dots,L-1\), read \(b=d(a)\), discard fixed points with \(b=a\), and then test whether the map returns from \(b\) to \(a\). When \(b \lt L\), that second value comes straight from the table. When \(b\ge L\), the code computes it immediately from the prime factorization of \(b\) by separating the factor 2 and then checking odd divisors up to \(\sqrt{b}\).

Phase 3: built-in sanity checks

All three implementations include the same lightweight checkpoints before producing the final answer: they verify \(d(220)=284\), \(d(284)=220\), and the partial case \(L=300\mapsto 504\). Those checks are useful because they exercise both the divisor-sum logic and the amicable-pair scan.

Complexity Analysis

The sieve phase uses \(O(L)\) space and \(O(L\log L)\) time. The outer scan over candidates is linear in \(L\). Whenever an out-of-range partner \(b\) appears, the factorization fallback costs \(O(\sqrt{b})\) time in the worst case, because the implementations test divisibility by 2 and then by odd integers up to the square root.

A faithful upper bound for the full algorithm is therefore

$O\!\left(L\log L+\sum_{\substack{2\le a\lt L\\d(a)\ge L}}\sqrt{d(a)}\right)$

time and \(O(L)\) space. In the Project Euler range the sieve clearly dominates in practice, which is why this method is much faster than factoring every number below the limit independently.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=21
2. Amicable numbers: Wikipedia - Amicable numbers
3. Aliquot sum: Wikipedia - Aliquot sum
4. Divisor function: Wikipedia - Divisor function
5. Perfect numbers: Wikipedia - Perfect number