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?

• pacmaninbw: Welcome to code review where we review working code and provide tips on how to improve that code. Is this code working as expected? When you say This is what I have so far it indicates that the code is not complete and therefore off-topic.
• maverick: The code is functional. But I don't think it is as efficient as it could be.

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.

• maverick: so something like palindrome = [int(str(x)+str(x)[::-1] for x in range(10,99)] to generate the list of palindromes.
• Samwise: range(10,100) I think, but yarp
• maverick: For replacing nested for loops, i tried it with iter = itertools.combinations_with_replacement(palindrome, 2) but looping through itfor x,y in iter: I get half the number of results as before. Am I missing something?
• Samwise: Are the ones you're missing flipped versions of ones you already have?
• maverick: That's possibly what's happening. Thank you for pointing me in the right direction

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.