Skip to content

Project Euler Problem 74

January 29, 2012

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
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: