Project Euler — Problem 92 Solution

Problem

A num­ber chain is cre­at­ed by con­tin­u­ous­ly adding the square of the dig­its in a num­ber to form a new num­ber until it has been seen before.

For exam­ple,

image

 

There­fore any chain that arrives at 1 or 89 will become stuck in an end­less loop. What is most amaz­ing is that EVERY start­ing num­ber will even­tu­al­ly arrive at 1 or 89.

How many start­ing num­bers below ten mil­lion will arrive at 89?

Solution

let max = 10000000

// build up a cache for all the numbers from 1 to 10 million
let cache = Array.init (max+1) (fun n ->
    match n with
    | 0 | 1 -> Some(false)
    | 89 -> Some(true)
    | _ -> None)

// define function to add the square of the digits in a number
let addSquaredDigits n =
    n.ToString().ToCharArray()
    |> Array.sumBy (fun c -> pown (int(c.ToString())) 2)

// define function to take an initial number n and generate its number chain until
// it gets to a number whose subsequent chain ends with 1 or 89, which means that
// all previous numbers will also end in the same number
let processChain n =
    let rec processChainRec n (list: int list) =
        if cache.[n] = None then processChainRec (addSquaredDigits n) (list@[n])
        else list |> List.iter (fun n' -> cache.[n'] <- cache.[n])
    processChainRec n []

// go through all the numbers from 2 to 10 million using the above function
[2..10000000] |> List.iter processChain

// how many numbers whose number chain ends with 89?
let answer = cache |> Array.filter (fun n -> n = Some(true)) |> Array.length

This is actu­al­ly a fair­ly sim­ple prob­lem, with the main chal­lenge being how to make it run fast enough to obey with the one minute rule which is where the cache comes in.

Using the prop­er­ty that if a chain start­ing with the num­ber n, i.e. n, n1, n2, …, ends in 89 then the chain start­ing with any of the num­bers n1, n2, … will also end in 89 we can min­imise the amount of com­pu­ta­tion required by caching pre­vi­ous results. Note I didn’t have to mark the cache as muta­ble in this case because the Array con­struct in F# is a fixed-sized, zero-index, muta­ble col­lec­tions of ele­ments.