Image of the glider from the Game of Life by John Conway
Skip to content

Largest Palindromic Number In Python

I found the absolute best way to learn the Python programming language, while at the same time, increasing deductive logic capacity and learning mathematics. The way is through Project Euler. Of course, you don't have to use the Python language to complete the problems. You can use any language you like, or use pencil and paper if that suits your needs best.

At any event, I'm going through the problems one by one, and have completed the first 4. The fourth problem took a great deal of thinking to get right, but I nailed it out slowly, and actually came up with a pretty fast solution. The problem is this:

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.

After hacking a bit, I realized that the only way I knew how to solve this problem, was to brute force it. Some things came to mind almost immediately:

  • I should start with 999 * 999 and count down, rather than 100 * 100 and count up, seeing as though I'm looking for the largest palindromic number.
  • 999 * 999 = 998001 iterations through every number, but I will be testing each one at least twice, so I only need to test half (999 * 999, 999 * 998, 999 * 997, ... 999*100, 998 * 998, 998 * 997, ... 998 * 100, 997 * 997, 997 * 996, ..., etc)
  • There should a pattern with palindromic numbers to further increase my algorithm.

Point 3 was the hardest for me to find, but I found it. There is in fact a pattern with 6-digit palindromic numbers (technically speaking, any even-digit palindrome (I know that my result will be 6-digits, or at least I'm fairly confident)). Consider the palindrome "abccba":

Let's look at the numeric column of each letter:

a(100,000) + b(10,000) + c(1,000) + c(100) + b(10) + a(1)

Adding similar variables (in algebraic notation):

100001a + 10010b + 1100c

The common denominator is 11:

11(9091a + 910b + 100c)

This means that each palindrome will be a multiple of 11.

This means that I can start with 999 * 990 for my first test, 999 * 979 for my second, 999 * 968 for my third, and so on. This will greatly reduce the number of iterations that I need to step through when finding this palindromic number. It wasn't long, however, that I realized this problem will need to be separated into two functions. One to determine if the number is in fact a palindrome, returning either True or False, and the second function to iterate through all the possible product combinations, filling an array with nothing but palindromic numbers. Here is my solution:

#!/usr/bin/env python
def is_palin(string):
    """Returns true if a string is a palindrome"""
    start, end = 0, len(string) - 1
    while end > start:
        if string[start] != string[end]:
            return False
        start += 1
        end -= 1
    return True

def palindrome():
    """Finds the largest palindrome that is the product of 2 3-digit numbers"""
    num1 = 999
    result_arr = []
    while num1 > 100:
        num2 = 990
        if num2 > num1:
            num2 = num1 - (num1 % 11)
        while num2 > 109:
            if is_palin(str(num1 * num2)):
                result_arr.append(num1 * num2)
            num2 -= 11
        num1 -= 1
    print result_arr[len(result_arr) - 1]


A couple comments about the code. First, I'm turning the number into a string, then determining if that string is in fact a palindrome. I look at the beginning and ending letter of the string. If they match, I increase the beginning letter by 1 and decrease the ending letter by one, and test again if they match. I continue to do this throughout the string until every letter was tested. If they all passed, return True, otherwise, return False. Second, to keep my algorithm only churning through half of the required iterations, I want to make sure that I start with the square, and work down from there. For example:

View with a monospace font, or this table won't make much sense (see the original post):

999*990    998*990    997*990    ...    990*990
999*979    998*979    997*979    ...    990*979    989*979    988*979    987*979    etc.
999*968    998*968    997*968    ...    990*968    989*968    988*968    987*968
  ...        ...        ...      ...      ...        ...        ...        ...
999*121    998*121    997*121    ...    990*121    989*121    988*121    987*121
999*110    998*110    997*110    ...    990*110    989*110    988*110    987*110

The only aspect about my algorithm, was that I am not breaking out when I find the largest palindromic number. The reason for this was simple- I got too caught up in churning through every 11 numbers, that I forgot to test when I found the largest. However, after looking at the code, I figured that I was curious about all the palindromes that I have found, so I stored them in an array then sorted it ascending. It is interesting to look through the array at each one, seeing the patterns throughout.

At any rate, on my machine, I benchmarked the code:

aaron@kratos:~$ time python

real    0m0.067s
user    0m0.068s
sys     0m0.000s

Nice and lean. 0.067 seconds isn't bad for a first attempt, I think. Thoughts? Comments?

{ 13 } Comments