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:
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:
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
After this, evaluating
amicables 10000 took