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