gistfile1.py

# We could iterate over factors and check for palindromes in their products,
# but this is slower than iterating over palindromes and trying to split them
# up[1]: the approach used here examines possible solutions in descending
# order, so we always find the biggest one first. This allows us to exit early.
#
# Either way, here's a definition for `is_palindrome` that ended up being
# unnecessary:
#
# def is_palindrome(x):
#     """Is the given positive integer x a palindromic number?"""
#     s = str(x)
#     return s == s[::-1]

def descending_sub_n_digit_palindromes(n):
    """Returns all palindromes with <= n digits, in descending order."""

    # The digits of an n-digit palindrome look like this:
    #
    # * If n is even we want the form abcddcba.
    #                                 ====      <- ceil(n / 2) digits
    # * If n is odd we want the form abcdedcba.
    #                                =====      <- ceil(n / 2) digits
    #
    # Either way, we count down ((n + 1) // 2)-digit numbers and append their
    # reverse string values; if n is odd, don't count the center digit twice.

    while n >= 0:
        k = (n + 1) // 2
        highest = 10 ** k - 1
        lowest = highest // 10

        for x in range(highest, lowest, -1):
            s_x = str(x)            # "abcde"
            rev = s_x[::-1]         # "edcba"

            # For odd n, skip the doubled center digit:
            if n % 2 == 1:
                rev = rev[1:]       # "dcba"

            yield int(s_x + rev)    # "abcdedcba"
        n -= 1


def find_largest_palindrome(n):
    """Finds the largest palindrome that can be written as the sum of two
    n-digit numbers."""

    # Highest possible n-digit factor.
    highest = 10 ** n - 1

    # The product of two n-digit numbers has no more than 2n digits:
    for p in descending_sub_n_digit_palindromes(2 * n):
        if p > highest ** 2:
            continue

        # Try to split p up into two factors. We want a >= p // a, otherwise
        # we consider each pair twice; this is why we only count down to
        # sqrt(p) inclusive. Since
        #
        #          highest // 10 < sqrt(p) <= p // a <= a <= highest,
        #
        # both numbers returned will have n digits.
        for a in range(highest, int(p ** .5) - 1, -2):
            if p % a == 0:
                return (a, p // a)


def print_largest_palindrome(n):
    """Formatting wrapper around find_largest_palindrome."""

    a, b = find_largest_palindrome(n)
    print('Largest palindrome found!  {} x {} = {}'.format(a, b, a * b))


n = int(input('How many digits in each factor? '))
print_largest_palindrome(n)

# [1]: (In fact, this appears to be the fastest palindrome product finding
#      function out there! On a slow laptop even find_largest_palindrome(7)
#      takes less than two seconds; results from various Project Euler blogs
#      across the internet seem to lie closer to 30 seconds, up to a minute.
#      The algorithm runs in O(sqrt(10^n)) time, I think, but I might be wrong,
#      so don't grade me on that statement.)