# Euler Solution 21

### From ProgSoc Wiki

# 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))