Project Euler #4 - Largest Palindrome Product

Question

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.

How would you improve the following code?

I'm looking specifically for:

• performance optimizations
• ways to shorten the code
• more "pythonic" ways to write it

---

   def is_palindrome(num):
        return str(num) == str(num)[::-1]        
    def fn(n):
        max_palindrome = 1
        for x in range(n,1,-1):
            if x * n < max_palindrome: 
                break
            for y in range(n,x-1,-1):
                if is_palindrome(x*y) and x*y > max_palindrome:
                    max_palindrome = x*y
                elif x * y < max_palindrome:
                    break
        return max_palindrome

    print fn(999)

Answer 1

The function is_palindrome converts num to a string twice. You might consider:

def is_palindrome(n):
   """Return True if n is a palindrome; False otherwise."""
   s = str(n)
   return s == s[::-1]

And then for the main loop I would write:

from itertools import product
max(x * y for x, y in product(range(1000), repeat=2) if is_palindrome(x * y))

This runs in less than a second so I think it is not worth putting lots of effort into optimizing it.

Answer 2

It looks good to me.

You could break from the inner loop even if x*y == max to avoid 1) an additional useless iteration 2) checking if it is a palindrome. Also it would remove some code testing the value of the product.

I think you could change the limits of the inner loop to consider only y smaller or equal to x. If you do so, you can break out of the outer loop if x*x < max.

Edit :

Some more details. My second optimisation tips is not a really a good tip, it's not a bad tip neither.

Here is the function before and after taking my second comment into action. Also, some more basic code has been added for benchmarking purposes.

def fn(n):
    itx,ity = 0, 0
    max_palindrome = 1
    for x in range(n,1,-1):
        itx+=1
        if x * n < max_palindrome:
            break
        for y in range(n,x-1,-1):
            ity+=1
            if is_palindrome(x*y) and x*y > max_palindrome:
                max_palindrome = x*y
            elif x * y < max_palindrome:
                break
    print "1", n,itx,ity,max_palindrome
    return max_palindrome

def fn2(n):
    itx,ity = 0, 0
    max_palindrome = 1
    for x in range(n,1,-1):
        itx+=1
        if x * x <= max_palindrome:
            break
        for y in range(x,1,-1):
            ity+=1
            if x*y <= max_palindrome:
                break
            if is_palindrome(x*y):
                max_palindrome = x*y
                break
    print "2", n,itx,ity,max_palindrome
    return max_palindrome

Now, when running the following tests :

for n in [99,999,9999,99999,999999]:
    assert fn(n) == fn2(n)

fn is sometimes in a pretty epic way, sometimes just worse...

fn n      itx    ity result
1 99       10     38 9009
2 99        6     29 9009
1 999      93   3242 906609
2 999      48   6201 906609
1 9999    100   4853 99000099
2 9999     51   2549 99000099
1 99999   339  50952 9966006699
2 99999   171 984030 9966006699
1 999999 1000 498503 999000000999
2 999999  501 250499 999000000999