Finding Amicable Numbers: A Project Euler Solution

I recently worked through the Project Euler problem on amicable numbers. Here's how I approached it and what I learned along the way.

What Are Amicable Numbers?

Amicable numbers are pairs where each number equals the sum of the other's proper divisors. A proper divisor is any divisor except the number itself.

Take 220 and 284:

• The proper divisors of 220 are: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110

• Their sum: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

• The proper divisors of 284 are: 1, 2, 4, 71, and 142

• Their sum: 1 + 2 + 4 + 71 + 142 = 220

Pythagoras knew about this first pair, and mathematicians have been finding more ever since.

The Problem

Find the sum of all amicable numbers under 10,000.

My Approach

I split this into three parts:

Calculating the Sum of Proper Divisors

python

def sum_of_divisors(n):
    sum_of_divisors = 0
    for i in range(1, n):
        if n % i == 0:
            sum_of_divisors += i
    return sum_of_divisors

This checks every number from 1 to n-1 and adds up the ones that divide evenly.

Pre-computing Results

Instead of recalculating divisor sums multiple times, I stored them in a dictionary:

python

dictionary_x = {}
for integer in range(1, 10001):
    dictionary_x[integer] = sum_of_divisors(integer)

This saves a lot of redundant computation.

Finding Amicable Pairs

python

amicable_sum = 0
for a in range(1, 10001):
    b = dictionary_x[a]
    if b < 10001 and b != a and dictionary_x.get(b) == a:
        amicable_sum += a

For each number a, I check if:

1. Its divisor sum b is within range

2. a and b are different (to exclude perfect numbers)

3. The divisors of b sum back to a

What I Learned

Caching is useful: Pre-computing the divisor sums made this much faster than recalculating them each time.

Watch for edge cases: The condition b != a prevents perfect numbers (like 6, where 1+2+3=6) from being counted incorrectly.

Dictionary lookups work well: Using .get() handles cases where b might be out of range.

Wrapping Up

This problem was a good exercise in combining basic number theory with practical coding techniques. The caching approach made the solution efficient enough to run quickly while keeping the code straightforward.

If you're working through Project Euler problems, this one is worth trying.