Fastest algorithm to find the largest palindrome that is the product of 2 numbers with the same number of digits

Question

How do I make this code run in under 30s to find the largest palindrome that is the product of 2 numbers with the same number of digits?

def palindrome(maxInt):
    pa=[]
    for x in range(maxInt,0,-1):
        for y in range(maxInt,0,-1):
            num=x*y
            if str(num) == str(num)[::-1]:
                pa.append(num)
    return max(pa)

maxInt is the largest number with the specified digits. For example if you want a palindrome that is a multiple of 2 3-digit numbers you maxInt would be 999. If you want the largest palindrome that is a multiple of 2 4-digit numbers maxInt would be 9999. etc.

If maxInt = 9, it should output 9.

If maxInt = 99, it should output 9009.

So if maxInt = 999, the programme should output 906609.

How do I make it return 99000099 for maxInt=9999 in under 30s

Answer 1

1. It gets faster if you fix that x>=y, so 99*91 and 91*99 will not be tested and found separately
2. When a palindrome is found, the inner loop can exit (as it is counting downwards, all palindromes it may find for the same x are certainly smaller than the "current" one)
3. If the current product is smaller than the current maximum, the inner loop can also exit
4. If x*x is smaller than the current maximum, the outer loop can exit too

---

def palindrome(maxInt):
    maxpal=0
    for x in range(maxInt,0,-1):
        if x*x<maxpal:                         # 4.
            break
        for y in range(x,0,-1):                # 1.
            num=x*y
            if num<maxpal:                     # 3.
                break
            if str(num) == str(num)[::-1]:
                maxpal=num
                break                          # 2.
    return maxpal

(Of course 3. could be in the range, for y in range(x,maxpal//x,-1): perhaps)

5. Strictly said, it should only check y-s having the same number of digits as x, which was not addressed yet, but ** and a downwards-rounded log10() can do that after all.

My current complete code:

import math,time

def palindrome(maxInt):
    maxpal=0
    for x in range(maxInt,0,-1):
        if x*x<maxpal:                                                     # 4.
            break
        for y in range(x,max(maxpal//x,10**int(math.log10(x))-1),-1):      # 1. 3. 5.
            num=x*y
            if str(num) == str(num)[::-1]:
                maxpal=num
                break                                                      # 2.
    return maxpal

start=time.time()
print(palindrome(9))
print(palindrome(99))
print(palindrome(999))
print(palindrome(9999))
print(palindrome(99999))
print(palindrome(999999))
print("%d seconds" % (time.time()-start))

Example output:

9
9009
906609
99000099
9966006699
999000000999
0.731034 seconds