Problem 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.

My first implementation:

top = 0
for x in xrange(100,1000):
    for y in xrange(x,1000):
        blarg = str(y * x)
        if blarg == blarg[::-1]:
            if y * x > top:
                top = y * x
print "Greatest ",top
# 0.334316968918 Typical execution time

There is relatively little that can be done to improve here, as no easy criteria exist to substantially improve what is already a fairly straightforward problem. However, one improvement can be made that improves the search time by a small margin:

top = 0
for x in xrange(999,100,-1):
    for y in xrange(999,x,-1):
        blarg = str(y * x)
        if blarg == blarg[::-1]:
            if y * x > top:
                top = y * x
print "Greatest ",top
# 0.310236930847 Typical execution time

Just by making our search start from the high end of our search range (That is, searching from 999 down to 100, rather than 100 up to 999), we can come across the solution a lot faster (fourth iteration, to be precise). However, this doesn't stop our program from continuing to search after already finding the answer. The only way we can make this execute faster from here is to narrow our search space.

Consider the smallest possible 6-digit (which we know our answer must be, since the smallest 7-digit number is the product of the first two four-digit numbers) palindromic number that is the multiple of two 3-digit numbers, which is 111111 (143 * 777). Since our product must be a palindrome, we can say that the digit in positions 1 and 6 must be the same, as well as the pairs in positions 2 and 5, and 3 and 4, respectively. To put this into polynomial form:

N = 100001x + 10010y + 1100z

For example, if we replace (x, y, z) with (5, 1, 4), we get N = 514415.
To simplify the equation, we can divide out a common factor of the three coefficients, the largest of which is 11:

N = 11(9091x + 910y + 100z)

This tells us something interesting about the space we're searching in: that if we take the prime factors of the 6-digit numbers that are palindromes, that one of the factors of one of the numbers is 11, since 11 is prime. Let's check this with some code:

for x in palis:
    if x % 11 == 0:
        print x,len(str(x)),"Factor of 11!"
    else:
        print x,len(str(x)),"Not factor of 11!"

In this code, the variable palis is a list of all palindromes generated by multiples of three-digit numbers. I'll leave it up to any experimental readers to generate their own copy of said list. Running this code with the proper input demonstrates that for the 6-digit entries in the list, all have a factor of 11, while the 5-digit entries do not.

Now that we know that our answer must have a factor of 11, we can use a condition to switch our search step from 1 to 11 when our first factor is not a multiple of 11.

top = 0
for x in range(999,100,-1):
    if x % 11 == 0:  
        step = -1
        roof = 999
    else:
        step = -11
        roof = 990
    for y in range(roof,x,step):
        prod = x * y
        if prod <= top:
            break
        prodstr = str(prod)
        if prod == prod[::-1]:
            top = prod
print "Greatest ",top
# 0.00324416160583 Typical execution time