# Problem 21 – Sum of amicable pairs

Here is my solution for the 21st Euler problem:

import List proper_divisors n = [ x | x <- [1..n], mod n x == 0, n /= x] amicable = sum [ x | x <- [1..10000], f(x)] where f x = let y = sum $ proper_divisors x z = sum $ proper_divisors y in x == z && x /= y main = print amicable

The big issue concerning this problem is the time required to calculate the proper divisors. I compiled the program using GHC with active profiling, and here are the results:

As one can see, most of the time running the program is spent on the *proper_divisors* function. That function could be optimized by, for example, calculating the proper divisors of all numbers first, and then just accessing them each time they are needed instead of calculating them twice, as I do in function *f*. Nevertheless, it only runs in 2,04 seconds, which is ok 🙂

Advertisements

Leave a Comment