Problem #95 concerns chains formed by repeatedly replacing a number with the sum of its proper factors. The question reads:
Project Euler Problem 95: Amicable chains
The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.
Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:
12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)
Since this chain returns to its starting point, it is called an amicable chain.
Find the smallest member of the longest amicable chain with no element exceeding one million.
My solution for this problem involves a ton of brute force. Here is my solution:
Solution #1: Brute Force Approach
First, we determine the sum of the proper factors of every number less than 1,000,000 by iterating through the possible divisors less than 500,000 and adding each divisor to every proper multiple of it. Next, we start from 1,000,000 and work down, checking each number for periodic behavior of amicable chains. We can perform this task dynamically, so numbers that are part of larger chains do not need to be checked multiple times. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #95
'''
import time
def projectEulerProblemNinetyFive(n):
properSums = [0]*(n+1)
for c in range(1,n/2+1):
for d in range(2*c,n+1,c):
properSums[d]+=c
maxLoop = 5
minNumber = 12496
loopLengths = [-1]*(n+1)
for e in range(n,0,-1):
if loopLengths[e]==-1:
t = 0
f = properSums[e]
loops = True
found = [e]
if(f!=e):
while(f!=e):
t+=1
if(f>n):
for x in found:
loopLengths[x] = 0
loops = False
break
if loopLengths[f]!=-1:
for x in found:
loopLengths[x] = loopLengths[f]
loops = False
break
if f in found:
a = found.index(f)
for x in found:
loopLengths[x] = len(found)-a
found = found[a:]
break
found.append(f)
v = properSums[f]
if(v==f or v==0):
for x in found:
loopLengths[x] = 0
loops = False
break
f = v
if loops:
for x in found:
loopLengths[x] = t
if t>maxLoop:
maxLoop = t
minNumber = found[0]
for x in found:
if x<minNumber:
minNumber = x
elif t==maxLoop:
for x in found:
if x<minNumber:
minNumber = x
else:
for x in found:
loopLengths[x] = 0
return minNumber
start = time.time()
print projectEulerProblemNinetyFive(1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
14316
--- 5.02517795563 seconds ---
for input of n = 1000000.
'''
And with that, we’re done. That took over 5 seconds to run. There must be a faster way to search for loops then the method I used. I definitely want to return to this problem at some point.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 