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)

• dm03514: whenever a product or combination or permutation is mentioned, i'd check itertools first

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

• blueberryfields: are you sure the second optimization is correct?
• SylvainD: 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.
• blueberryfields: y is in the range [n..x-1]. yx > xx for y > x
• blueberryfields: 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
• SylvainD: I've added more details about what I had in mind.