# ac65fcda590f

`Problem 74`
author Steve Losh Mon, 27 Feb 2017 01:15:50 +0000 45b4d825074f 82da42a326e4 (none) src/euler.lisp

## Changes

```diff -r 45b4d825074f -r ac65fcda590f src/euler.lisp
--- a/src/euler.lisp	Mon Feb 27 00:51:33 2017 +0000
+++ b/src/euler.lisp	Mon Feb 27 01:15:50 2017 +0000
@@ -1427,6 +1427,45 @@
(mod <> (expt 10 10))))

+
+(defun problem-74 ()
+  ;; The number 145 is well known for the property that the sum of the factorial
+  ;; of its digits is equal to 145:
+  ;;
+  ;; 1! + 4! + 5! = 1 + 24 + 120 = 145
+  ;;
+  ;; Perhaps less well known is 169, in that it produces the longest chain of
+  ;; numbers that link back to 169; it turns out that there are only three such
+  ;; loops that exist:
+  ;;
+  ;; 169 → 363601 → 1454 → 169
+  ;; 871 → 45361 → 871
+  ;; 872 → 45362 → 872
+  ;;
+  ;; It is not difficult to prove that EVERY starting number will eventually get
+  ;; stuck in a loop. For example,
+  ;;
+  ;; 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
+  ;; 78 → 45360 → 871 → 45361 (→ 871)
+  ;; 540 → 145 (→ 145)
+  ;;
+  ;; Starting with 69 produces a chain of five non-repeating terms, but the
+  ;; longest non-repeating chain with a starting number below one million is
+  ;; sixty terms.
+  ;;
+  ;; How many chains, with a starting number below one million, contain exactly
+  ;; sixty non-repeating terms?
+  (labels ((digit-factorial (n)
+             (sum (mapcar #'factorial (digits n))))
+           (term-count (n)
+             (iterate (for i :initially n :then (digit-factorial i))
+                      (until (member i prev))
+                      (collect i :into prev)
+                      (counting t))))
+    (iterate (for i :from 1 :below 1000000)
+             (counting (= 60 (term-count i))))))
+
+
;;;; Tests --------------------------------------------------------------------
(def-suite :euler)
(in-suite :euler)```