# dd8289802cda

`Problem 63`
author Steve Losh Sat, 04 Mar 2017 17:57:27 +0000 6dd2cb3e5f27 0061265e6b73 (none) src/euler.lisp

## Changes

```--- a/src/euler.lisp	Sat Mar 04 12:04:57 2017 +0000
+++ b/src/euler.lisp	Sat Mar 04 17:57:27 2017 +0000
@@ -2028,6 +2028,26 @@
((> score target) (removef candidates first)))) ; tricksy hobbitses
(thereis (apply (nullary #'min) candidates))))))

+(defun problem-63 ()
+  ;; The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the
+  ;; 9-digit number, 134217728=8^9, is a ninth power.
+  ;;
+  ;; How many n-digit positive integers exist which are also an nth power?
+  (flet ((score (n)
+           ;; 10^n will have n+1 digits, so we never need to check beyond that
+           (iterate (for base :from 1 :below 10)
+                    (for value = (expt base n))
+                    (counting (= n (digits-length value)))))
+         (find-bound ()
+           ;; it's 21.something, but I don't really grok why yet
+           (iterate
+             (for power :from 1)
+             (for maximum-possible-digits = (digits-length (expt 9 power)))
+             (while (>= maximum-possible-digits power))
+             (finally (return power)))))
+    (iterate (for n :from 1 :below (find-bound))
+             (sum (score n)))))
+

(defun problem-74 ()
;; The number 145 is well known for the property that the sum of the factorial
@@ -2160,6 +2180,7 @@
(test p60 (is (= 26033 (problem-60))))
(test p61 (is (= 28684 (problem-61))))
(test p62 (is (= 127035954683 (problem-62))))
+(test p63 (is (= 49 (problem-63))))

(test p74 (is (= 402 (problem-74))))```