20 August 2010

Project Euler : Find the sum of all the numbers that can be written as the sum of 5th powers of their digits.

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:
1634 = 1^(4) + 6^(4) + 3^(4) + 4^(4)
8208 = 8^(4) + 2^(4) + 0^(4) + 8^(4)
9474 = 9^(4) + 4^(4) + 7^(4) + 4^(4)
As 1 = 1^(4) 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 (in Ruby)

This problem is a bit tricky and can be solved with a trial and error method. Best way to attack this problem is to first arrive at a solution for the 4th power as given in the problem, convince ourselves that the solution that we have coded is correct. Then run the same for 5th powers. Of course the upper bound is a mystery, but who cares you have trial and error to know the answer.

final_result = 0
2.upto(200000) do |x|
  sum = x.to_s.split(//).inject(0){|b,i| b+i.to_i**5}
  final_result += sum if sum == x
end
puts "The magic sum is #{final_result}"

HOVER HERE TO SEE THE SOLUTION!!

Cheers!!
Bragaadeesh

No comments: