Fastest algorithm to find the largest palindrome that is the product of 2 numbers with the same number of digits
- It gets faster if you fix that
x>=y
, so99*91
and91*99
will not be tested and found separately - 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) - If the current product is smaller than the current maximum, the inner loop can also exit
- 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)
- Strictly said, it should only check
y
-s having the same number of digits asx
, which was not addressed yet, but**
and a downwards-roundedlog10()
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