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