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)