Problem 4: Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Understanding the problem

The maximum number obtained by multipliying two 3-digit numbers is:



In [40]:

    
N = 999 * 999
print(N)

We should find a polindrome p that not exceed N The primer digit of this number is 9. So, we should find the a number < N with the last number a 9 Let's try with the number p1 = N - 2



In [41]:

    
p1 = N - 2
print(p1)

Almost a polindrome! Fist and last digit are equal and the bigests (9). Se second and fith are also equal and biggest (9) We should decrease the number by 200 so that it become a polindrome



In [42]:

    
p2 = p1 - 200
print(p2)

This is a palindrome!!!! Now it should be decomposed into two 3-digit number If not possible, then the next polindrome should be obtained and calculate the factors again



In [43]:

    
def factor(N):
    for i in xrange(2,N):
        if (N % i == 0):
            return i
    return 0



In [44]:

    
def decompose(N):
    f = factor(N)
    lf = []
    while f > 0:
        lf.append(f)
        N = N / f
        #print("Factor: {}, Rest: {}".format(f, N)) #-- Debuging
        f = factor(N)
    lf.append(N)
    print("Factors:{}".format(lf))



In [45]:

    
decompose(996699)









    



Factors:[3, 11, 30203]

The problem is that many of these palindromes do not have two 3-digit factors. It is better to study another approach

Second approach

Start by iterating over the two factors. Every factors should go from 100 (the minimul) to 999. Perform all the multiplications and get a list with all the palindroms. A function for knowing if a number is a palindrom should be implemented. Finally get the maximum number in that list



In [46]:

    
#-- Function for detecting if a 5-6 digit number is a palindrome
def is_palindrome(n):
    #-- Convert the number into a string
    s = str(n)
    if s[0] != s[-1]:
        return False  #--- Not a palindrome for sure
    if s[1] != s[-2]:
        return False  #--- Not a palindrome for sure
    if len(s)==5:
        return True   #-- A palindrome!
    else:
        if s[2]==s[3]:
            return True
        return False



In [47]:

    
is_palindrome(99699)









    Out[47]:





True

Get a list with all the 3-digit factors palindromes



In [48]:

    
l = []
for i in range(100,1000):
    for j in range(i, 1000):
        n = i * j
        if is_palindrome(n):
          l.append(i*j)



In [49]:

    
len(l)









    Out[49]:





1239

Calculate the maximum palindrome



In [54]:

    
sol = max(l)
print(sol)

Let's check



In [51]:

    
decompose(sol)









    



Factors:[3, 11, 83, 331]

Let's group the factors:



In [52]:

    
f1 = 331 * 3
f2 = 83 * 11



In [55]:

    
print ("{} = {} * {}".format(sol, f1, f2))









    



906609 = 993 * 913



In [ ]: