Sunday, May 30, 2010

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

We must find an upper limit for numbers to search.  As the length of a number increases, 9**5 is the greatest additional contribution a digit can make to the sum of 5th power digits. Meanwhile, the number itself is increasing by powers of 10, which will eventually overcome the rate of increase given summing 5th powers of digits.  So, when we find that the sum of 5th power digits of 9999999 (of length 7) equals 413343 (of length 6), we can be sure that no higher number can produce 5th power digit sum of sufficient length.  (a non-rigorous proof, I know).

let problem30a =
    let powdigsum n e = n |> string |> Seq.map(string >> int32) |> Seq.sumBy(fun i -> pown i e)
    {2..9999999}
    |> Seq.filter(fun n -> (powdigsum n 5) = n)
    |> Seq.sum

No comments:

Post a Comment