# 0d2671fa1875

Problem 23

author | Steve Losh <steve@stevelosh.com> |
---|---|

date | Tue, 21 Feb 2017 21:08:17 +0000 |

parents | 6e9dc46857b5 |

children | d7c65f771582 |

branches/tags | (none) |

files | src/euler.lisp |

## Changes

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