Euler Project 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

My Solution

(defun factorial(n)

(remove-if #'(lambda(x) (null x)) (loop for i from 1 to (- n 1)

collect (if (zerop (rem n i))

i))))

(defun enumerate-interval (low high)

(loop for i from low to high

collect i))

(defun Euler21(n)

(remove-if-not #'(lambda(x)(let ((result (apply #'+ (factorial x))))

(and

(= x (apply #'+ (factorial result)))

(not (= x result)))))

(enumerate-interval 1 n)))

Others' Solution

First Solution

(defun list-divisors (n)
(loop for i from 1 to (sqrt n)
when (= (mod n i) 0)
collect i
and unless (= i (/ n i))
collect (/ n i)))

(defun sum-of-restricted-divisors (n)
(- (reduce #'+ (list-divisors n)) n))

(defun sum-of-amicable-pairs (limit)
(loop for n from 1 to limit
for m = (sum-of-restricted-divisors n)
when (and (not (= m n))
(= (sum-of-restricted-divisors m) n))
sum n))
(sum-of-amicable-pairs 10000)

Second Solution

(defun euler-21 ()
(let ((max-n 10000) (table (make-hash-table)))
(loop for n from 1 below max-n
do (let ((d (apply #'+ (hah::factors n))))
(when (< d max-n) (push n (gethash d table)))))
(loop for n from 1 below max-n
sum (apply #'+
(mapcar (lambda (v)
(if (and (/= v n)
(member n (gethash v table))) v 0))
(gethash n table))))))

Third Solution

(defun problem-21 (n)

(labels ((sum-div (z)
(reduce #'+ (remove z (divisors z)))))

(loop for x from 1 to n
for a = (sum-div x)
for b = (sum-div a)
if (and (= x b) (not (= a x))) sum x)))

(defun divisors (x)
(loop for y from 1 to (sqrt x)
for z = (/ x y)
when (integerp z) collect y and collect z))