Aug
7
In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 30.
There’s not much new happening here. Again, the solution is pretty straight-forward. One minor hold up came with the way the problem statement was written. You’ll notice the max number to test wasn’t called out. I didn’t worry about this fact too much, but as you’ll see in the comments below, I solved the problem up to 9^4*5, 9^5*5 and then 9^6*5 and the last two tries provided the same result. I did try 9^7*5 as well but I didn’t wait for that result to come back. In the end, you’ll see I ended up using 9^5*5 as my max test value.
As always, any feedback is welcome.
# Euler 30
# http://projecteuler.net/index.php?section=problems&id=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.
timer_start = Time.now
# The result of 5, 6, and (I'm guessing) 7 nines was the same.
# Therefore only iterating upto 9**5 * 5
max, sum_all_sums = 9**5 * 5, 0
(2..max).each do |i|
sum = i.to_s.chars.inject(0){|sum, char| sum + (char.to_i ** 5)}
sum_all_sums += i if (i == sum)
end
puts sum_all_sums
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
I actually put most of my effort into computing a reasonable upper bound. My basic idea was to look for the point where the number was too high to possibly be a sum of its digits to the fifth power. I think my limit actually came to 9**5 * 6 so that slows down the solution a bit.
def sum_of_digits?(n, power) n == n.to_s.split(//).inject(0) {|sum, digit| sum += (digit.to_i ** power) } end def get_upper_bound(power) base = 9 ** power digit_count = 2 upper_bound = 0 while (digit_count += 1) do return upper_bound if ((digit_count * base).to_s).length < digit_count upper_bound = digit_count * base end end puts (10..get_upper_bound(5)).select {|n| sum_of_digits?(n, 5)}.inject {|sum, x| sum + x}Thanks, Greg, for filling in the details which I blatantly disregarded. Good stuff.