Euler Solution 95

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 95

Find the smallest member of the longest amicable chain with no element exceeding one million.

Python by Althalus

Runtime ~17 minutes

No doubt there is much to be done to optimise this, but I am lazy.

from time import time
start = time()

import psyco
psyco.full()

def get_divisors(n):
    divisors = [1,]
    for x in xrange(2,(int(n**0.5)+1)):
        res,rem = divmod(n,x)
        if rem == 0:
            divisors.append(x)
            divisors.append(res)
    return divisors

def do_chain(n):
    chain = []
    while n not in chain:
        chain.append(n)
        n = sum(get_divisors(n))
        if n > 999999: return -1,chain
        if n == 0: return -1,chain
    if n != chain[0]: return -1,chain
    return (len(chain),chain)

longest_chain = 0 
smallest_element=1000000

for x in xrange(12496,1000000):
    length,chain = do_chain(x)
    if length > longest_chain:
        longest_chain = length
        chain.sort()
        smallest_element = chain[0]
print smallest_element
print time() - start
Personal tools