Practically every Project Euler problem benefits from memoization, however the issues I ran into with #34 had nothing to do with my algorithm.
The first hurdle was figuring out the upper bound. After scratching around in my notebook, I figured any number I would be looking for would have 7 digits or less. That gives us an upper bound of 9! * 7.
The second hurde took me much, much longer to figure out.
Here’s the secret: 0! = 1
I had taken it for granted that 0! would (of course!) be 0, and I had pre-filled my cache with the number 0. I went round, and round, and round, and round, and round, and round before figuring out (quite accidentally) my error.
It doesn’t make any sense to me, but you can’t argue with math!
Find the sum of all numbers which are equal to the sum of the factorial of their digits.
# cache the digit factorials factorials =  (1..9).each do |i| factorials.push(i * factorials.last) end result = 0 (3..2_540_160).each do |n| sum = n.to_s.split("").inject(0) do |sum,n| sum + factorials[n.to_i] end result += n if n == sum end puts result
Runs in just under a minute 🙂