Puzzled over palindromic product problem

Question

I've been learning Ruby, so I thought I'd try my hand at some of the project Euler puzzles. Embarrassingly, I only made it to problem 4...

Problem 4 goes as follows:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

So I figured I would loop down from 999 to 100 in a nested for loop and do a test for the palindrome and then break out of the loops when I found the first one (which should be the largest one):

final=nil
range = 100...1000
for a in range.to_a.reverse do
  for b in range.to_a.reverse do
    c=a*b
    final=c if c.to_s == c.to_s.reverse
    break if !final.nil?
  end
  break if !final.nil?
end
puts final

This does output a palindrome 580085, but apparently this isn't the highest product of two three-digit numbers within the range. Strangely, the same code succeeds to return 9009, like in the example, if I change the range to 10...100.

• Can someone tell me where I am going wrong?
• Also, is there a nicer way to break out of the internal loop?

Thanks

Answer 1

You are testing 999* (999...100), then 998 * (999...100)

Hence you will be testing 999 * 500 before you test 997 * 996.

So, how you we find that right number?

First note the multiplication is reflective, a * b == b * a, so b need not go from 999...0 every time, just a ...0.

When you find a palindrone, add the two factors together and save the sum (save the two factors also)

Inside the loop, if (a+b) is ever less than the saved sum, abandon the inner loop and move to the next a. When a falls below sum/2, no future value you could find would be higher than the one you've already found, so you're done.