Had a slice of free time, so decided to look at the next problem. Here’s the initial naive solution:

```
divisors n = [x | x <- [1 .. n-1], n `mod` x == 0]
isAbundant n = n < (sum $ divisors n)
abundants n = filter isAbundant $ [1 .. n]
expressSum z nums = not $ null [(x,y) | x <- nums, y <- nums, x + y == z]
sumAbundants n =
let a = abundants n in
sum $ filter (\x -> not $ expressSum x a) [1 .. n]
```

While it gave the correct answer, it did so in `3133.33`

seconds, which is … embarrassing.

This is just *too* inefficient, even the following …

```
(defun divisors (n)
(loop for i from 1 below n
when (= 0 (mod n i))
collect i))
(defun abundantp (n)
(< n
(reduce #'+ (divisors n))))
(defun abundants (n)
(loop for i from 1 below n
when (abundantp i)
collect i))
(defun possible-summands (z nums)
(loop for x in nums do
(loop for y in nums
when (= z (+ x y)) do
(return-from possible-summands (cons x y)))))
(defun sum-abundants (n)
(let* ((ab (abundants n))
(summands
(loop for i from 1 to n
when (null (possible-summands i ab))
collect i)))
(reduce #'+ summands)))
```

… takes no less than half as long, at `1329.168`

seconds.

BTW why is `28123`

the upper limit for this sequence? I had no idea, and found this explanation (and tangentially, this one too).

Anyway, I’m ashamed to say I didn’t put in the effort to learn how to profile Haskell programs (*next time ?*) and profiled the Lisp version instead, which showed that (**duh**) all the time was going in finding divisors. Obviously, we can just loop till the *square root of N* instead of looping *all the way to N*. After this change:

```
(defun divisors (n)
(declare (type fixnum n))
(loop for i from 1 below (floor (sqrt n))
when (= 0 (mod n i))
collect i))
```

… it runs in `38 milliseconds`

!!

And a similar change to the Haskell version:

```
divisors :: Int -> [Int]
divisors n = [x | x <- [1 .. round $ sqrt $ fromIntegral n], n `mod` x == 0]
```

gave the expected answer in `180 milliseconds`

. Not bad (though it should be noted we’re still an order of magnitude away in efficiency).

**Notes:**

Haskell makes it very easy to quickly arrive at a

*correct*solution, but the road from there to an*efficient*solution is less clear.The brevity of the notation helps, but I get a feeling it’s also due to the single-letter variable names – which is all right (and indeed well-suited) for a tiny math problem, but unclear whether it’ll hold up for code in a large-scale project.

People usually jump to the [“Programming Language shootout”](), but if the code

*there*is any indication, writing performant Haskell code is a dark art, and*the three-line quicksort is a devilish honeytrap*.