Project Euler Problem 74

Ivar Thorson bio photo By Ivar Thorson

Problem 74 concentrates yet again on factorials, sums of digits, and chains of computation. To be honest, I am pretty sick of this type of problem, so here is my inelegant brute force solution.

(def factorial-char (zipmap "0123456789"
                            (conj (reductions * (iterate inc 1)) 1)))

(defn next-element [n] (reduce + (map factorial-char (str n))))

(defn chain-length 
  ([n] (chain-length n #{n}))
  ([n m] (let [o (next-element n)]
           (if (m o)
             (count m)
             (recur o (conj m o))))))

(defn euler-74 [n]
  (count (filter #(= 60 (chain-length %)) (range n))))

(time (euler-74 1000000)) ;; "Elapsed time: 56503.206202 msecs"

Once again the computation takes only slightly less than a minute, so my algorithm clearly needs improvement.