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.
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 thein 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
abccba = 11 \ (9091a + 910b + 100c).
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!