# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1488158150 0
# Node ID ac65fcda590f7c83abff02c5fc7b6e2fb7f1377d
# Parent  45b4d825074f384881c2b2b5fc8e0fec423d3bf7
Problem 74

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)