60 Days of Euler in F# - Problem 30

The Problem

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

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 included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

The Solution

This one is pretty easy. The trickiest part is the requirement that we find "the sum of all the numbers". Since there are an infinite number of integers, we first have to figure out where to stop.

95 is 59049. Eventually we will get to a number of digits n such that 10n > 95*n. It turns out that n is 6. So we only have to concern ourselves with numbers less than a million.

We'll start by cracking a number into its digits, raising those to the 5th power, and getting the sum.

let digitize n =
    let str = sprintf "%i" n
    str |> Seq.map (fun x -> int(x) - int('0'))

let pow5 n = n*n*n*n*n

let powsum n =
    digitize n
    |> Seq.map pow5
    |> Seq.sum

The digitize function takes a number, converts it to a string, and then converts the individual characters in that string to digits.

The pow5 function multiples n by itself to get the 5th power. For 5th powers, this is about twice as fast as the built-in pown function. For higher powers, it might not be. I haven't tested it.

Finally, powsum puts the other two functions together to find the sum of the 5th powers of the digits of a number.

Now we can solve the problem:

let isSumOfPowers n = 
    powsum n = n

#time
seq { 2..999999 }
|> Seq.filter isSumOfPowers
|> Seq.sum
#time

The above finds all the numbers between 2 and 999999 that meet the problem definition and sums them.

Other Posts in This Series