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: