Project Euler: Problem #4 – Largest palindrome product

largest palindrome

Largest palindrome1 product

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

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

First approach

I started by the brute-force method to find this mysterious number.  First, with a double loop, make all the possible products with numbers from 100 to 999. Then, convert this product in a string to index each element one by one. It is possible improve this step, but we will talk about it later.

Compare the first digit with the last one, the second with the next to the last and so forth. If this test fails, pass to another product. Otherwise, save the palindrome number in a list.

Finally, take the largest in the list.

This is my first implementation:

#Create a sequence from 100 to 999
three_dig_seq = range(999, 99)
# and an empty list for the palindromes
list_palindromes = []
 
# loop twice over the number sequence
for n1 in three_dig_seq:
    for n2 in three_dig_seq:
        # Get the product
        number = n1 * n2
        # Transform it in string
        number = str(number)
        length_number = int(len(number)/2)
        # Compare each 'letter' to check if
        # it's a palindrome
        for i in range(length_number):
            if number[i] != number[-i - 1]:
                number_is_palindrom = False
                break
        else:
            number_is_palindrom = True
        # Add the number if it's indeed
        # a palindrome
        if number_is_palindrom:
            list_palindromes.append(int(number))
 
print max(list_palindromes)

However, Python has a very intuitive way to slice lists and we could use it to make a better test for palindromes.

Using lists and slices

Briefly, for a list called my_list, we could index it by my_list[start:end:step]. Thus, if we slice the list with a step equal to -1, we get the elements of my_list reversed. For a more pedagogic explanation, I recommend you the python documentation (Common Sequence Operations).

To check if a string is a palindrome or not we have only to check if number == number[::-1].

#Create a sequence from 100 to 999
three_dig_seq = range(999, 100)
# and an empty list for the palindromes
list_palindromes = []
 
# loop twice over the number sequence
for n1 in three_dig_seq:
    for n2 in three_dig_seq:
        # Get the product
        number = n1 * n2
        # Transform it in string
        number = str(number)
        # Check the whole string to test
        # if it's a palindrome
        if number == number[::-1]:
            # Add the palindrome to the list
            list_palindromes.append(int(number))
 
print list_palindromes
print 'Maximum Palindrome number', max(list_palindromes)

We can go further with a more mathematically solution. We know that our palindrome has to have 6 digits2 with the form $abccba$.  Factorizing and simplify this number, we get
\begin{equation*}
abccba = 11 \ (9091a + 910b + 100c).
\end{equation*}

So, we need to search the largest number divisible by 11 below 998001. I did not make this version, but it should be easy.

Until the next problem, eulerians!

Go back to the list of problems.


  1. In English we say that a number is a  palindrome or palindromic if the number remains intact when we reverse all its digits. In Spanish we have a very interesting word for this phenomena  capicúa.
  2. We are looking for a value between 100×100 = 10000 to 999×999 = 998001. 

Comments

  1. Chris Giles

    The largest palindrome less than 998001 using this formula is 997799, which is the product of a 2 digit number and a 4 digit number.
    It looks as if the formula finds palindromes with a factor of 11 and something else, finds products of 2 digits with 4 digits as well as 2 three digit numbers.
    Fails the test.

    1. Post
      Author
      Maikol Solís

      I don’t know where is the problem. In this case, a = 9, b=9 and c = 7, thus,

      11 * ( 9091 * 9 + 910 * 9 + 100 * 7 ) = 997799.

      Best.

Leave a Reply