euler 21 amicable numbers

Jan 31, 2015  

Picking up where I left off, apparently 2 years ago !! :(

To avoid a procrastination excuse, I decided to skip the step of adding it to the github repo I had started earlier. Here is the raw, unedited form of the attempt at the next problem in my sequence, #21.

isDiv a b = a `mod` b == 0

divisors n = [x | x <- [1 .. n-1], isDiv n x]

-- d(n) = sum of divisors of n
sumDiv n = sum $ divisors n

-- a and b are 'amicable' if d(a) = b, and d(b) = a
amicable a b = (a /= b) && (sumDiv a == b) && (sumDiv b == a)

-- evaluate all pairs under 1000
-- amicableUnder1000 = [(x,y) | x <- [1 .. 999], y <- [1 .. 999], amicable x y]
-- euler21 = foldr (\(x,y) -> x + y) 0  amicableUnder1000

This naive version was predictably going to take forever, so interrupted Ghci and decided to try a slightly different approach (to explicitly pre-evaluate the sums of divisors).

sumDivNumbersUnder10000 = [sumDiv n | n <- [1 .. 9999]]
sumDiv' n = sumDivNumbersUnder10000 !! (n-1)

amicable' (a,sa) (b,sb) = (a /= b) && (sa == b) && (sb == a)

amicableUnder10000 = [(x,y) | x <- [1 .. 9999], y <- [1 .. 9999], amicable' (x,sumDiv' x) (y, sumDiv' y)]

This version took 4.64 seconds in Ghci for the numbers less than 1000, at which point I realized the problem had actually called for the numbers less than 10000 instead. I left it running, out of curiosity, and it took 1758.96 seconds (not to mention a prodigious amount of memory: 97202052160 bytes!)

This done, the final answer was easy:

sum $ map fst amicableUnder10000
31626

But this sort of gets to my problem with Haskell; I’m never sure what’s really going on, and how to make it do what I want it to do. On the other hand, I can feel an excess of “imperative thinking” is getting in the way (why isn’t this as fast as a nested for loop?) Obviously, I need more time at this :)

Anyway, I tried yet another way towards this:

partialAmicable x n = [(x,y) | y <- [1 .. n-1], amicable' (x, sumDiv' x) (y, sumDiv' y)]

fullAmicable n = filter (not . null) (map f $ take n [1 ..])
             where f x = partialAmicable x n

… which ran into *** Exception: Prelude.(!!): index too large

At this point I realized that:

  • I had no idea how to ‘debug’ this (lacking a ‘stack trace’), but also
  • I was still dealing with lists, when I really wanted vectors.

So I gave it one final shot:

import Data.Vector as V

divSums n = V.fromList [sumDiv x | x <- [1 .. n-1]]

amicables n = let ds = divSums n in
                  V.fromList [(x,y) | x <- [1 .. n-1], y <- [1 .. n-1], amicable' (x, ds ! (x-1)) (y, ds ! (y-1))]

… and this time, I got

λ> amicables 10000
fromList [(220,284),(284,220),(1184,1210),(1210,1184),(2620,2924),(2924,2620),(5020,5564),(5564,5020),(6232,6368),(6368,6232)]
(204.01 secs, 97203591888 bytes)

Ok, I can stop here; perhaps 204 seconds of brute-forcing isn’t all that bad?

Unfortunately, my “comfort zone” yielded this:

(defun div (x y)
  (= (mod x y) 0))

(defun divisors (x)
  (loop for i from 1 below x
     when (div x i)
       collect i))

(defun sum-divs (x)
  (reduce #'+ (divisors x)))


(defun pre-sum-divs (n)
  (let ((myarr (make-array n :element-type 'fixnum)))
    (loop for i from 1 below n
	 do (setf (aref myarr i) (sum-divs i)))
    myarr))


(defun amicablep (x sx y sy)
  (and (not (= x y))
       (= sx y)
       (= sy x)))

(defun amicables (n)
  (let ((ds (pre-sum-divs n)))
    (loop for i from 1 below n do
	 (loop for j from 1 below n
	    when (amicablep i (aref ds i) j (aref ds j))
	    do (print j)))))

which runs just a little bit faster (!!)

CL-USER> (time (amicables 10000))

284
220
1210
1184
2924
2620
5564
5020
6368
6232
Evaluation took:
2.815 seconds of real time
2.820000 seconds of total run time (2.820000 user, 0.000000 system)
100.18% CPU
7,318,463,192 processor cycles
3,939,984 bytes consed

So this is my problem: I need to find a way to get my mental model of Haskell to perform at this speed (and clearly, it’s two orders of magnitude off). It isn’t going to be easy …

EDIT: Make that just one order of magnitude. It’s possible for Ghci to use compiled object code instead of byte code, by entering :set -fobject-code. After this, evaluating amicables 10000 took 23.71 seconds.