# Project Euler Problem 74

Project Euler Problem 74 solution may reuse functions **digitFact **and **asSumOfDigitsFact** from our Project Euler Problem 34 solution.

Now, we can come up with a function chainLen that calculates the length of chain for chained sums of digit factorials. If we simply build this chain recursively, then for the majority of cases the signal to stop would be reaching a number that chains into itself; few exceptions that involve a loop of length more, than one, are given in the problem description: for **169**, **363601**, and **1454 **the loop length is **3**; for pairs **(871,45361)** and **(872,45362)** the loop lengths are both **2**.

It is also apparent that we can calculate chain length for each number only once, and then reuse already found lengthes in chain calculations for other numbers. A very simple array-based **cache** will be sufficient. We also can prepopulate our cache with known exceptions for chain lengths.

Otherwise, the approach to the solution is straightforward – for each number of the given interval the length of the chain is calculated; then all lengths other, than 60, are filtered out; and finally those that left of length 60 are counted.

let digitFact = function | 0 | 1 -> 1 | 2 -> 2 | 3 -> 6 | 4 -> 24 | 5 -> 120 | 6 -> 720 | 7 -> 5040 | 8 -> 40320 | 9 -> 362880 | _ -> failwith "bad argument" let asSumOfDigitsFact n = Seq.unfold (fun x -> if x = 0 then None else Some(digitFact (x%10), x/10) ) n |> Seq.sum let cache = Array.zeroCreate ((asSumOfDigitsFact 999999) + 1) cache.[169] <- 3; cache.[363601] <- 3; cache.[1454] <- 3 cache.[871] <- 2; cache.[872] <- 2; cache.[45361] <- 2; cache.[45362] <- 2; let chainLen n = let rec buildChain prev len = match asSumOfDigitsFact prev with | x when x = prev -> len | _ as x -> match cache.[x] with | 0 -> buildChain x len + 1 | _ as l -> len + l match cache.[n] with | 0 -> let len = buildChain n 1 cache.[n] <- len len | _ as x -> x let problem074() = [1..999999] |> List.map chainLen |> List.filter (fun x -> x = 60) |> List.length