Project Euler Problem 21
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
Solution
Answer: 31626
We need all amicable numbers below $10000$.
Define $d(n)$ as the sum of proper divisors of $n$.
Two numbers $a,b$ form an amicable pair if:
$$d(a)=b,\qquad d(b)=a,\qquad a\ne b$$
Example:
$$d(220)=284,\qquad d(284)=220$$
So both 220 and 284 are included.
A direct approach:
- Compute $d(n)$ for every $n<10000$.
- For each $a$:
- let $b=d(a)$
- if $b\neq a$ and $d(b)=a$, then $a$ is amicable.
- Sum all such $a$.
Efficient divisor summation can be done by iterating divisors up to $\sqrt n$.
Python code:
def divisor_sum(n):
if n == 1:
return 0
total = 1
p = 2
while p * p <= n:
if n % p == 0:
total += p
q = n // p
if q != p:
total += q
p += 1
return total
LIMIT = 10000
d = [0] * LIMIT
for i in range(1, LIMIT):
d[i] = divisor_sum(i)
answer = 0
for a in range(1, LIMIT):
b = d[a]
if b != a and b > 0:
if b < LIMIT:
if d[b] == a:
answer += a
else:
if divisor_sum(b) == a:
answer += a
print(answer)
Known amicable pairs under $10000$:
$$(220,284),\ (1184,1210),\ (2620,2924),\ (5020,5564),\ (6232,6368)$$
Summing all numbers:
$$220+284+1184+1210+2620+2924+5020+5564+6232+6368 = 31626$$
Answer: 31626