Project Euler: Problem 4

http://projecteuler.net/index.php?section=problems&id=4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

First I tried a brute force method: iterate over unique pairs of three digit numbers and store the largest product palindrome.

def f1(n):
    res = 0

    for a in xrange(10**n - 1, 10**(n-1) - 1, -1):
        for b in xrange(a, 10**(n-1) - 1, -1):
            if str(a*b) == str(a*b)[::-1]:
                res = max(res,a*b)

    return res

I coded this to take in the number of digits for the input pairs. I don't know why; it seemed like the thing to do. This gets the answer, but brute force is usually a bad choice.

For my next iteration, I tried adding in some sanity checks to the a,b iterators. Specifically: if a*b is less than the current best answer, break out of the b iteration and decrement a. Furthermore, of a*a is less than the current best answer, stop altogether.

def f3(n):
    res = 0

    for a in xrange(10**n - 1, 10**(n-1) - 1, -1):
        if a*a < res:
            break

        for b in xrange(a, 10**(n-1) - 1, -1):
            if a*b < res:
                break

            if str(a*b) == str(a*b)[::-1]:
                res = max(res,a*b)

    return res

Much better! On my set-up, f1(3) returns in about 0.44 seconds. The better optimized version, f3(3), returns in about 0.0075 seconds.

As a final note, the largest palindrome made from the product of two 6-digit numbers is 999000000999. The largest palindrome made from the product of two 8-digit numbers is 9999000000009999. Nice symmetry!