# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1487711297 0
# Node ID 0d2671fa1875ae81a377d1c65a74cde33eb7f912
# Parent  6e9dc46857b5b9a285fa07ff992883a6510dbbc6
Problem 23

diff -r 6e9dc46857b5 -r 0d2671fa1875 src/euler.lisp
--- a/src/euler.lisp	Tue Feb 21 20:32:36 2017 +0000
+++ b/src/euler.lisp	Tue Feb 21 21:08:17 2017 +0000
@@ -60,7 +60,10 @@
   (sort (iterate (for i :from 1 :to (sqrt n))
                  (when (dividesp n i)
                    (collect i)
-                   (collect (/ n i))))
+                   (let ((j (/ n i)))
+                     ;; don't collect the square root twice
+                     (unless (= i j)
+                       (collect j)))))
         #'<))
 
 (defun proper-divisors (n)
@@ -101,6 +104,16 @@
            (multiplying i)))
 
 
+(defun perfectp (n)
+  (= n (sum (proper-divisors n))))
+
+(defun abundantp (n)
+  (< n (sum (proper-divisors n))))
+
+(defun deficientp (n)
+  (> n (sum (proper-divisors n))))
+
+
 ;;;; Problems -----------------------------------------------------------------
 (defun problem-1 ()
   ;; If we list all the natural numbers below 10 that are multiples of 3 or 5,
@@ -601,6 +614,35 @@
                   (enumerate (read-names) :start 1))
              (sum (* position (name-score name))))))
 
+(defun problem-23 ()
+  ;; A perfect number is a number for which the sum of its proper divisors is
+  ;; exactly equal to the number. For example, the sum of the proper divisors of
+  ;; 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect
+  ;; number.
+  ;;
+  ;; A number n is called deficient if the sum of its proper divisors is less
+  ;; than n and it is called abundant if this sum exceeds n.
+  ;;
+  ;; As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest
+  ;; number that can be written as the sum of two abundant numbers is 24. By
+  ;; mathematical analysis, it can be shown that all integers greater than 28123
+  ;; can be written as the sum of two abundant numbers. However, this upper
+  ;; limit cannot be reduced any further by analysis even though it is known
+  ;; that the greatest number that cannot be expressed as the sum of two
+  ;; abundant numbers is less than this limit.
+  ;;
+  ;; Find the sum of all the positive integers which cannot be written as the
+  ;; sum of two abundant numbers.
+  (let* ((limit 28123)
+         (abundant-numbers
+           (make-hash-set :initial-contents
+                          (remove-if-not #'abundantp (range 1 (1+ limit))))))
+    (flet ((abundant-sum-p (n)
+             (iterate (for a :in-hashset abundant-numbers)
+                      (when (hset-contains-p abundant-numbers (- n a))
+                        (return t)))))
+      (sum (remove-if #'abundant-sum-p (range 1 (1+ limit)))))))
+
 
 ;;;; Tests --------------------------------------------------------------------
 (def-suite :euler)
@@ -628,6 +670,7 @@
 (test p20 (is (= 648 (problem-20))))
 (test p21 (is (= 31626 (problem-21))))
 (test p22 (is (= 871198282 (problem-22))))
+(test p23 (is (= 4179871 (problem-23))))
 
 
 ;; (run! :euler)