Python: Find pairs of numeric palindromes that sum up to another palindrome

Question

I am trying to identify and print pairs of 4 digit palindromes that sum up to a 5 digit palindrome.

This is what I have so far

def isPalindrome(x):
    return str(x)==str(x)[::-1]

palindrome = [x for x in range(1000, 10000) if isPalindrome(x)]

for x in palindrome:
    for y in palindrome:
        if (9999 < x+y < 100000) and isPalindrome(x+y):
            print(x, y, x+y)

I am estimating the time complexity for this to be O(n^2),because I am traversing the list twice. Is it possible to improve on this?

Answer 1

Two opportunities for optimization that suggest themselves to me:

1. Seems like you should be able to produce an exhaustive list of 4-digit palindromes by taking every 2-digit number and then appending its mirror to it, rather than having to iterate through every 4-digit number and throw most of them out. That would let you build your palindrome list in about one-hundredth the time (you'll be iterating over 90 two-digit numbers instead of 9000 four-digit numbers in that first loop).

2. A lot of the sums you're checking will be too small (i.e. they'll be 4 digits); none will be too big (9999+9999=19998). You can minimize the work you do on those sums by iterating from largest to smallest and breaking the inner loop once the sum gets too small.

An alternative to the nested for loops would be using one of the itertools functions to generate all the combinations as a set of tuples, but I don't think that'd get you any performance wins.

Answer 2

Instead of using the isPalindrome function to determine if x + y is a length five palindrome, you can create the set of all length five palindromes in the range [10000, 20000) and check for set membership instead. Use the efficient method suggested by Sam Stafford to generate them.

This does not change the time complexity, but should be faster.