Project Euler — Problem 30 Solution

Problem

Sur­pris­ing­ly there are only three num­bers that can be writ­ten as the sum of fourth pow­ers of their dig­its:

1634 = 14 + 64 + 34 + 44

8208 = 84 + 24 + 04 + 84

9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not includ­ed.

The sum of these num­bers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the num­bers that can be writ­ten as the sum of fifth pow­ers of their dig­its.

Solution

// get the digits of a number into an array
let getDigits (n:bigint) = n.ToString().ToCharArray() |> Array.map (fun c -> bigint.Parse(c.ToString()))

// get the sum of a number's digits to the specified power
let getDigitsToPowerSum (n:bigint) pow = 
    getDigits(n) |> Array.map (fun x -> pown x pow) |> Array.sum

// get the max sum achievable by a number of the given number of digits to the specified power
let upperBound (digits:int) pow = bigint(digits) * pown 9I pow

// find the last number of digits n, where the max sum achievable by the digits of a number of
// n digits to the specified power is greater than the smallest number of n digits
// any number with more than n digits do not need to be checked
let digitsToCheck pow =
    let n =
        Seq.unfold (fun state -> Some(state, (state+1))) 1
        |> Seq.filter (fun x -> (upperBound x pow).ToString().ToCharArray().Length < x)
        |> Seq.head
    n-1

// get the next number with the given number of digits
let maxNumber digits = [1..digits] |> List.map (fun x -> 9I * pown 10I (x-1)) |> List.sum

let answer =
    let max = maxNumber (digitsToCheck 5)
    [2I..max] |> List.filter (fun n -> n = getDigitsToPowerSum n 5) |> List.sum

One of the tricky things with this prob­lem is that there’s no upper lim­it to how far you’d need to test before you can safe­ly deter­mine that you’ve test­ed all the num­bers whose sum of fifth pow­ers of their dig­its MIGHT be equal to the num­bers them­selves.

But that’s not to say it’s not pos­si­ble, for a 1-dig­it num­ber, i.e. 1..9, the max sum of its dig­its is 1 * (9 POW 5) = 59049; sim­i­lar­ly for a 2-dig­it num­ber the max sum is 2 * (9 POW 5) = 118098. The upper­Bound func­tion cal­cu­lates this upper ceil­ing for a num­ber of a giv­en dig­its and pow­er.

Let’s take a clos­er look at the dis­tri­b­u­tion of this upper lim­it as the num­ber of dig­its go up, for the fourth pow­er:

image

so as you can see, when the num­ber of dig­its reach­es 6, the max sum of fourth pow­ers of dig­its is 39366, but the small­est 6-dig­it num­ber is 100000! There­fore it’s impos­si­ble for any 6 dig­it num­ber to be writ­ten as the sum of fourth pow­ers of its dig­its, and it means we’ll need to go as far as cov­er­ing all 5 dig­it num­bers. The dig­it­sToCheck func­tion sim­ply encap­su­lates this bit of log­ic:

image

The maxNum­ber func­tion is a helper func­tion which gen­er­ates the biggest num­ber of the giv­en num­ber of dig­its. To find the answer, I sim­ply had to make use of all the helper func­tions men­tioned so far and sum the num­bers whose fifth pow­ers of its dig­its equals itself.