Skip to content

Problem 21 – Sum of amicable pairs

May 9, 2010

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: