# 5effe1bc7876

`Problem 21`
author Steve Losh Fri, 17 Feb 2017 13:07:45 +0000 137ba2e799c4 7c082c0289d5 (none) src/euler.lisp

## Changes

```--- 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)```