# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# 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)