Puzzled over palindromic product problem

Question

Hi,

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

The mistake is you assume that if you find palindrom with greatest a value it will give the greatest product it isn't true. Solution is to keep max_product value and update it against solution you find.

Answer 2

I can answer your first question: You need to find the highest product, not the product containing the highest factor. In other words a * b could be greater than c * d even if c > a > b.

Answer 3

The problem is that you might find a palindrome for an a of 999 and a b of 200, but you break too soon, so you never see that there is one for 998*997 (just example numbers).

You need to either look for all palindromes or once you find the first one, set that b as your minimum bound and continue looking through the a loop.

Answer 4

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.

Answer 5

You're breaking on the first palindrome you come to, not necessarily the biggest.

Say you have A,B,C,D,E. You test E * A before you test D * C.

Answer 6

Regarding the second question, my advice is to approach the problem in more functional, than procedural manner. So, rather than looping, you may try to "describe" your problem functionally, and let Ruby does the work:

• From all the pairs of 3-digit numbers,
  • select only those whose product is a palindrome,
    • and find the one with the largest product

Although this approach may not yield the most efficient of the solutions, it may teach you couple of Ruby idioms.

Answer 7

an implementation:

max = 100.upto(999).inject([-1,0,0]) do |m, a|
  a.upto(999) do |b|
    prod = a * b
    m = [prod, a, b] if prod.to_s == prod.to_s.reverse and prod > m[0]
  end
  m
end
puts "%d = %d * %d" % max

prints 906609 = 913 * 993

Answer 8

The main thing is to go through all the possible values. Don't try to break when you find the first answer just start with a best answer of zero then try all combinations and keep updating best. The secondary thing is to try to reduce the set of "all combinations".

One thing you can do is limit your inner loop to values less than or equal to a (since a*b == b*a). This puts the larger value of your equation always in a and substantially reduces the number of values you have to test.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

The next thing you can do is break out of the inner loop whenever the product is less than the current best value.

c = a*b
next if c < best

Next, if you're going to go through them all anyway there's no benefit to going through them in reverse. By starting at the top of the range it takes a while before you find a palindromic number and as a result it takes a while to reduce your search set. If you start at the bottom you begin to increase the lower bound quickly.

for a in range.to_a do
    for b in (100..a).to_a do

My tests show that either way you try some 405K pairs however. So how about thinking of the problem a different way. What is the largest possible product of two 3 digit numbers? 999 * 999 = 998001 and the smallest is 100*100 = 10000. How about we take the idea you had of breaking on the first answer but apply it to a different range, that being 998001 to 10000 (or 999*999 to 100*100).

for c in (10000...998001).to_a.reverse do

We get to a palindrome after only 202 tests... the problem is it isn't a product of two 3-digit numbers. So now we have to check whether the palindrome we've found is a product of 2 3-digit numbers. As soon as we find a value in the range that is a palindrome and a product of two 3-digit numbers we're done. My tests show we find the highest palindrome that meets the requirement after less than 93K tests. But since we have the overhead of checking that all palindromes to that point were products of two 3-digit numbers it may not be more efficient than the previous solution.

So lets go back to the original improvement.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

We're looping rows then columns and trying to be efficient by detecting a point where we can go to the next row because any additional trys on the current row could not possibly be better than our current best. What if, instead of going down the rows, we go across the diagonals?

Since the products get smaller diagonal by diagonal you can stop as soon as you find a palindome number. This is a really efficient solution but with a more complex implementation. It turns out this method finds the highest palindrome after slightly more than 2200 trys.

Answer 9

Consider the digits of P – let them be x, y and z. P must be at least 6 digits long since the palindrome 111111 = 143×777 – the product of two 3-digit integers. Since P is palindromic:

P=100000x + 10000y + 1000z + 100z + 10y + x
P=100001x + 10010y + 1100z
P=11(9091x + 910y + 100z)

Since 11 is prime, at least one of the integers a or b must have a factor of 11. So if a is not divisible by 11 then we know b must be. Using this information we can determine what values of b we check depending on a.