# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1487336865 0
# Node ID 5effe1bc78768e1643475166b6b804b07e290f55
# Parent  137ba2e799c49f368aa1c5c5f360270d185150dd
Problem 21

diff -r 137ba2e799c4 -r 5effe1bc7876 src/euler.lisp
--- a/src/euler.lisp	Fri Feb 17 12:53:27 2017 +0000
+++ b/src/euler.lisp	Fri Feb 17 13:07:45 2017 +0000
@@ -48,12 +48,14 @@
           (not (dividesp n 11))) nil)
     (t (definitely-palindrome-p n))))
 
+
 (defun sum (sequence &key key)
   (iterate (for n :in-whatever sequence)
            (sum (if key
                   (funcall key n)
                   n))))
 
+
 (defun divisors (n)
   (sort (iterate (for i :from 1 :to (sqrt n))
                  (when (dividesp n i)
@@ -61,6 +63,9 @@
                    (collect (/ n i))))
         #'<))
 
+(defun proper-divisors (n)
+  (remove n (divisors n)))
+
 (defun count-divisors (n)
   (* 2 (iterate (for i :from 1 :to (sqrt n))
                 (counting (dividesp n i)))))
@@ -551,6 +556,26 @@
   ;; Find the sum of the digits in the number 100!
   (sum (digits (factorial 100))))
 
+(defun problem-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.
+  (labels ((sum-of-divisors (n)
+             (sum (proper-divisors n)))
+           (amicablep (n)
+             (let ((other (sum-of-divisors n)))
+               (and (not= n other)
+                    (= n (sum-of-divisors other))))))
+    (sum (remove-if-not #'amicablep (range 1 10000)))))
+
 
 ;;;; Tests --------------------------------------------------------------------
 (def-suite :euler)
@@ -576,6 +601,7 @@
 (test p18 (is (= 1074 (problem-18))))
 (test p19 (is (= 171 (problem-19))))
 (test p20 (is (= 648 (problem-20))))
+(test p21 (is (= 31626 (problem-21))))
 
 
 ;; (run! :euler)