euler 23 non abundant sums

Feb 1, 2015  

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.