Euler #4 in Python

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.

http://projecteuler.net/problem=4

Below is my solution to this problem. It works, but I noticed another solution that used

if x*y < max_seen: continue

like this:

def biggest():
    big_x, big_y, max_seen = 0, 0, 0
    for x in xrange(999,99,-1):
        for y in xrange(x, 99,-1): 
            if x*y < max_seen: continue
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

What I don't get is how that line works. The first time through max_seen = 0 and the first x*y is 999*999 which is greater than 0. So that condition isn't met and the next line is run. Makes sense. Eventually, however, max_seen will be larger than x*y so why does it continue here?

It seems this line isn't even needed because if the condition is or isn't met the program will continue anyway. I suspect I'm not understanding how continue works in Python.

This is my approach:

def find_biggest():
    big_x, big_y, new_pal, max_seen = 0, 0, 0, 0
    for x in range(999, 100, -1):
        for y in range(x, 100, -1):
            if is_palindrome(x*y) == True:
                new_pal = x*y
                if new_pal > max_seen:
                    big_x, big_y, max_seen = x, y, new_pal

From an efficiency standpoint the program should exit as soon as all new x*y are < max_seen, but 999*100 is less than 998*900 (meaning it couldn't stop yet as it still needs to check 998*y, 997*y, etc.) so how would you code that?

Answer 1

I suspect the reason that the code checks for x*y < max_seen first is that it is an easier test than is_palindrome. If you expect many of your potential x and y values to be no good, it makes sense to do the easiest tests first so that you only need to run the complicated tests a few times.

That said, if x*y < max_seen is true, there won't be any successful tests for the current x value. An optimization could be to replace continue (which goes on to the next y value) with break (which ends the inner loop and so goes on to the next x value).

You could even do something similar for the outer loop, and test if x * 999 < max_seen. If so, you'll never find a better result and you can stop looping. Here's how that would look in code:

def biggest():
    big_x, big_y, max_seen = 0, 0, 0
    for x in xrange(999,99,-1):
        if x*x < max_seen:
            break # breaks out of outer loop, as no later x value can be better
        for y in xrange(x, 99,-1): 
            if x*y < max_seen:
                break # breaks out of inner loop, no later y value can be better
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y
    return big_x, big_y, max_seen

Answer 2

The two approaches are almost the same although the first approach avoids checking the palindrom if the product is smaller than the biggest palindrom already encountered, therefore more efficient.

if x*y < max_seen: continue
if is_palindrome(x*y):
   ...

To answer your first question, in the first approach, max_seen will get large only if it belongs to a palindrom, so it will not eventually get large.

Answer 3

Here is an efficient general solution (~5x faster than others):

def pgen(factor):
    ''' Generates stream of palindromes smaller than factor**2 
    starting with largest possible palindrome '''
    pmax = str(factor**2)
    half_palindrome = int(pmax[0:len(pmax)/2]) - 1
    for x in xrange(half_palindrome, 0, -1):
        yield int(str(x) + str(x)[::-1])

def biggest(factor):
    ''' Returns largest palindrome and factors '''
    for palindrome in pgen(factor):
        for f1 in xrange(factor/11*11, factor/10, -11):
            f2 = palindrome/f1
            if f2 > factor:
                break
            if f2*f1 == palindrome:
                return palindrome, f1, f2

>>> biggest(99)
(9009, 99, 91)
>>> biggest(999)
(906609, 993, 913)
>>> biggest(9999)
(99000099, 9999, 9901)
>>> biggest(99999)
(9966006699L, 99979, 99681L)
>>> biggest(9999999)
(99956644665999L, 9998017, 9997647L)
>>> biggest(99999999)
(9999000000009999L, 99999999, 99990001L)
>>> biggest(999999999)
(999900665566009999L, 999920317, 999980347L)