Euler Solution 21

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 21

Given the function d(n) that finds the proper divisors of n. An amicable pair a and b are defined by d(a) = b and d(b) = a, where a <> b.

Find the sum of all the amicable pairs in the range 1 to 10000

Haskell by SanguineV

Runtime: 9.832 seconds

{- Function to return the list of proper divisors of a number not including itself. -}
divisors :: Integer -> [Integer]
divisors n = filter (\x -> n `mod` x == 0) [1 .. floor (( fromIntegral n)/2)]

{- For each number starting at 220 (known smallest amicable pair number) go to 10000
 - checking each in turn. Then add up the resulting list of those that are amicable.
 - NOTE: Line broken up for clarity, single line to compile. -}
main = print (sum (filter 
       (\x ->
          (\y -> (not (x == y)) && (x == (sum (divisors y))))
       (sum (divisors x)))
       [220..10000]))

Python by Althalus

Runtime: 474 ms

from math import sqrt

#Return a list containing all factors of the number passed.
def getFactors(num):
    list = [1,] #For this problem, the list of proper divisors includes 1, but not the original number. (odd...)
    for i in range(2,int(sqrt(num)+1)):
        if num%i == 0:
            list.append(i)
            list.append(num/i)
    return list
#check if a number is amicable (ie, sum of factors of a = b and sum of factors of b = a
def isAmicable(num, pair=0):
    factor_sum = sum(getFactors(num)) #Get sum of factors
    if pair==0:#if pair = 0, only 1 number was passed to the function. 
        return isAmicable(factor_sum,num) #Pass the sum and this number to the function again
    else: #two numbers? Compare them. If the number is different to it's "pair", 
          #and if it's factors equal it's pair, they are amicable.
        if num != pair and factor_sum == pair:
            return True
    return False

amicables = []
#Build a list of amicables.
for i in range(1,10000):
    if isAmicable(i) and i not in amicables: amicables.append(i)

print(sum(amicables))
Personal tools