# HG changeset patch # User Steve Losh # Date 1487787819 0 # Node ID 793042f215fb102a250f164430156fa9c07e89c5 # Parent d2de8990952fb9b646e05d3b5d8e15fbfafd2d07 Problem 30 diff -r d2de8990952f -r 793042f215fb src/euler.lisp --- a/src/euler.lisp Wed Feb 22 18:08:30 2017 +0000 +++ b/src/euler.lisp Wed Feb 22 18:23:39 2017 +0000 @@ -55,6 +55,12 @@ (funcall key n) n)))) +(defun product (sequence &key key) + (iterate (for n :in-whatever sequence) + (multiplying (if key + (funcall key n) + n)))) + (defun divisors (n) (sort (iterate (for i :from 1 :to (sqrt n)) @@ -844,6 +850,36 @@ (b :from 2 :to 100))) (adjoining (expt a b))))) +(defun problem-30 () + ;; Surprisingly there are only three numbers that can be written as the sum of + ;; fourth powers of their digits: + ;; + ;; 1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴ + ;; 8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴ + ;; 9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴ + ;; + ;; As 1 = 1⁴ is not a sum it is not included. + ;; + ;; The sum of these numbers is 1634 + 8208 + 9474 = 19316. + ;; + ;; Find the sum of all the numbers that can be written as the sum of fifth + ;; powers of their digits. + (flet ((maximum-sum-for-digits (n) + (* (expt 9 5) n)) + (digit-power-sum (n) + (sum (mapcar (rcurry #'expt 5) (digits n))))) + (iterate + ;; We want to find a limit N that's bigger than the maximum possible sum + ;; for its number of digits. + (with limit = (iterate (for digits :from 1) + (for n = (expt 10 digits)) + (while (< n (maximum-sum-for-digits digits))) + (finally (return n)))) + ;; Then just brute-force the thing. + (for i :from 2 :to limit) + (when (= i (digit-power-sum i)) + (summing i))))) + ;;;; Tests -------------------------------------------------------------------- (def-suite :euler) @@ -878,6 +914,7 @@ (test p27 (is (= -59231 (problem-27)))) (test p28 (is (= 669171001 (problem-28)))) (test p29 (is (= 9183 (problem-29)))) +(test p30 (is (= 443839 (problem-30)))) ;; (run! :euler)