# Project Euler #4 - Largest Palindrome Product

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)

• whenever a product or combination or permutation is mentioned, i'd check itertools first Sep 29 '13 at 1:16

## 2 Answers

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.

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

• are you sure the second optimization is correct? Sep 26 '13 at 22:33
• Assuming x goes from n to 0 and y goes from x to 0, I think we have the following property: 1) for a given x, xy is decreasing 2) if xx <= max, xy <= xx <= max. Sep 26 '13 at 23:43
• y is in the range [n..x-1]. yx > xx for y > x Sep 27 '13 at 1:11
• that's a change which leads to an incorrect algorithm (as written above, it would miss some of the larger palindromes, including the correct solution). It would be an effective optimization if i was writing an algorithm looking for the smallest palindrome, though Sep 27 '13 at 4:40
• I've added more details about what I had in mind. Sep 29 '13 at 22:49