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.

Answer 2

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 3

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 4

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.

Answer 5

C# Implementation :

using System;

namespace HighestPalindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            int m = 1;
            bool flag = false;

            while (true)
            {
                if (flag) j = m + 1;
                else j = m;

                for (i = m; i > 0; i--)
                {
                    Console.WriteLine("{0} * {1} = {2}", 1000 - i, 1000 - j, (1000 - i) * (1000 - j));
                    j++;

                    //--- Palindrome Check ------------------------------

                    int number, temp, remainder, sum = 0;
                    number = temp = (1000 - i) * (1000 - j);

                    while (number > 0)
                    {
                        remainder = number % 10;
                        number /= 10;
                        sum = sum * 10 + remainder;
                    }

                    if (sum == temp)
                    {
                        Console.WriteLine("Highest Palindrome Number is - {0} * {1} = {2}", 1000 - i, 1000 - j, temp);
                        Console.ReadKey();
                        return;
                    }

                    //---------------------------------------------------
                }

                if (flag)
                    m++;
                flag = !flag;
            }

        }
    }
}

Answer 6

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 7

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 8

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 9

ar=[]
limit = 100..999
for a in limit.to_a.reverse do
  for b in (100..a).to_a.reverse do
    c=a*b
    if c.to_s == c.to_s.reverse
      palndrm=c 
      ar << palndrm
    end  
  end
end
print ar
print"\n"
puts ar.max
puts ar.min 

Answer 10

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 11

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 ab == ba). 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 12

Here's what I came up with in Ruby:

def largest_palindrome_product(digits)
  largest, upper, lower = 0, 10**digits - 1, 10**(digits - 1)

  for i in upper.downto(lower) do
    for j in i.downto(lower) do
      product = i * j
      largest = product if product > largest && palindrome?(product)
    end
  end
  largest
end

And here's the function to check if the number is a palindrome:

def palindrome?(input)
  chars = input.to_s.chars
  for i in 0..(chars.size - 1) do
    return false if chars[i] != chars[chars.size - i - 1]
  end
  true
end

I guess there's probably a more efficient solution out there, though.

Answer 13

For this problem, as we are looking for the highest palindrom, i assumed it would start with a 9. Thus ending with a 9 (palindrom).

if you pay attention, to get a number finishing by 9, you can only get it with numbers finishing by 9 and 1, 3 and 3, 7 and 7.

Then it is useless to check the other values (for instance 999*998 as it will not end with a 9).

Starting from 999 and 991, you can then substract 10 to 991, trying 999 and 981 etc... You do the same with 993 and 993 ... 993 * 983 same with 997 * 997 then 997 * 987 etc You don't need to go further than 900 or 10^4 - 10^3 as you can be sure the highest will be before.

int PB4_firstTry(int size)
{
    int nb1 = (int)pow(10.0,size+1.0) - 1, nb2 = (int)pow(10.0,size+1.0) - 1;
    int pal91 = getFirstPalindrome(size,9,1);
    int pal33 = getFirstPalindrome(size,3,3);
    int pal77 = getFirstPalindrome(size,7,7);

    int bigger1 = (pal91 > pal33) ? pal91 : pal33;
    return (bigger1 > pal77) ? bigger1 : pal77;
}

int getFirstPalindrome(int size,int ending1,int ending2)
{
    int st1 =  (int)pow(10.0,size+1.0) - 10 + ending1;
    int comp = st1 - pow(10.0,size);
    int st2 =  (int)pow(10.0,size+1.0) - 10 + ending2;
    int answer = -1;
    while (st1 > comp)
    {
        for (int i = st2; i > comp && st1*i > answer; i-=10)
        {
            if (PB4_isPalindrome(st1*i))
                answer = st1*i;
        }
        st1 -= 10;
    }
    return answer;
}

bool PB4_isPalindrome(int number)
{
    std::string str = intToString(number);
    for (int i = 0; i < (int)(str.length() / 2); i++)
    {
        if (str[i] != str[str.length() - 1 - i])
            return false;
    }
    return true;
}

std::string intToString(int number)
{
    std::ostringstream convert;
    convert << number;
    return convert.str();
}

Of course, this works for 4 size digits factors etc.