Problem #21 features an obscure type of number known as an amicable number. The problem reads:
Project Euler Problem 21: Amicable numbers
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71, and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.
When I first attempted this problem, I instantly thought of using a sieve to find the sum of the proper divisors of every number less than 10,000. Unfortunately, this sieve is not perfect, as any amicable numbers with a sum greater than 10,000 will be missed. As a result, I used the following solution:
Solution #1: Semi-Sieve Approach
I used a sieve to find the sum of the proper divisors of every number less than 10,000 and stored each sum in an array. After this, I added any numbers which were guaranteed to be amicable based on my array to a running total. Any numbers with a sum greater than 10,000 would be added to an array of potential amicable numbers. Then I used a separate function made specifically to add the proper divisors of any given number to manually check each of the potential amicable numbers. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Semi-Sieve Approach to Project Euler Problem #21
'''
import time
from math import sqrt
def addProperDivisors(n):
temp = n
p = []
e = []
c = 2
while(c<=sqrt(n)):
if(n%c==0):
t = 0
while(n%c==0):
n/=c
t+=1
p.append(c)
e.append(t)
c+=1
if(n>1):
p.append(n)
e.append(1)
total = 1
powers = len(p)
for x in range(powers):
powerSum = 0
for i in range(e[x]+1):
powerSum+=(p[x]**i)
total*=powerSum
return total - temp
def projectEulerProblemTwentyOne(n):
sums = [0]*n
i = 1
while(i<=n/2):
for c in range(2*i, n, i):
sums[c]+=i
i+=1
total = 0
potential = []
for x in range(n):
value = sums[x]
if(value>=n):
potential.append(x)
elif(value>0 and value!=x and sums[value] == x):
total+=x
for x in potential:
if(addProperDivisors(addProperDivisors(x)) == x):
total+=x
return total
start = time.time()
print projectEulerProblemTwentyOne(10000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
31626
--- 0.0148520469666 seconds ---
for input of n=10000
'''
And with that, we’re done. The semi-sieve approach was efficient for a relatively small limit of 10,000. I may return to this problem to find a more efficient solution eventually.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 