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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/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
    result_arr.sort()
    print result_arr[len(result_arr) - 1]

palindrome()

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 palindrome.py
906609

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

  1. Justin using Firefox 2.0.0.6 on Ubuntu | September 15, 2007 at 4:19 pm | Permalink
    1
    2
    3
    def is_palin(num):
        s = str(num)
        return s == s[::-1]
  2. Peter using Firefox 2.0.0.6 on Ubuntu | September 15, 2007 at 7:06 pm | Permalink

    A few thoughts:

    - 5 digit palindromes are not necessarily divisible by 11, though that doesn't matter too much here as we're looking for 6 digit ones
    abcba = 10001a + 1010b + 100c

    - quick one liner (takes a few seconds here)

    1
    max([x*y for x in range(100,1000) for y in range(100,1000) if str(x*y)==str(x*y)[::-1]])
  3. Seth using Firefox 2.0.0.6 on Mac OS | September 15, 2007 at 7:23 pm | Permalink

    Never seen Project Euler before. Thanks for posting about it. :-)

  4. Aaron using Debian IceWeasel 2.0.0.6 on Debian GNU/Linux 64 bits | September 15, 2007 at 7:56 pm | Permalink

    @Peter- Ahh, yes. Good call. I've updated my post to reflect the change.

    @Seth- No problem. Let me know how far you get. :)

  5. Duccio using Konqueror 3.5 on Kubuntu | September 16, 2007 at 12:38 am | Permalink

    Good post...only a doubt.
    When you reach the column of the table of multiple of 11 (990,979,etc.) i think you must multiplicate this number for all the numbers smaller than this, and not only for multiple of 11 smaller than this. For example I don't see 990*989,990*988,etc. that are multiple of 11 too. Don't you think?

  6. phoenyx using Firefox 2.0.0.6 on Windows XP | September 16, 2007 at 2:13 am | Permalink

    FYI, it's considered bad form to post answers to problems outside of the forum.

  7. Athropos using Firefox 2.0.0.6 on Ubuntu | September 16, 2007 at 5:52 am | Permalink

    You should use the timeit module when you need to time something. It's better than using the time command because you then don't measure the startup time of the Python interpreter which can be a big part of the total time.

    1
    2
    3
    4
    5
    6
    import timeit

    ...

    t1 = timeit.Timer('palindrome()', 'from __main__ import palindrome')
    print t1.timeit(20)
  8. i dont know using Opera 9.52 on Windows XP | September 11, 2008 at 8:50 am | Permalink

    what's are biggest 2 3-dgits palindrome?

  9. leed using Firefox 3.1b1 on Windows XP | October 26, 2008 at 3:29 am | Permalink

    I think follow code is the fastest I have tried.
    maxnum = 0
    for i in range(990, 99, -11):
    for j in range(999, i, -1):
    num = i * j
    if num <= maxnum:
    break
    else:
    strnum = str(num)
    if strnum == strnum[::-1]:
    maxnum = num
    break
    print maxnum

  10. vince using Firefox 3.0.6 on Windows XP | March 16, 2009 at 12:45 pm | Permalink

    999 * 999 = 998001 iterations through every number, but I will be testing each one at least twice, so I only need to test half.

    This point is an error if you consider the first one where you only go until 100.

    Following your first point, means that you only do 999 * 900 iterations as opposed to 999 * 999. Why? you stop at 100. This means that you don't consider 999 * 99, 999 * 98, and so on.

    Remember: the number of digits from 100 to 999 = (999 - 100) + 1 = 900.

  11. vince using Firefox 3.0.6 on Windows XP | March 16, 2009 at 12:46 pm | Permalink

    Actually, you only perform 900 * 900 my mistake.

  12. vince using Firefox 3.0.6 on Windows XP | March 16, 2009 at 12:47 pm | Permalink

    actually, you only perform 900 * 900

  13. Nicholas using Safari 536.25 on Mac OS | August 31, 2012 at 10:14 am | Permalink

    Another thing to remember: If you want a number that starts with 9, and it's a palindrome, you should only try numbers that can come out with 9's if you follow a multiplication table. That means only try with the following sets in the last slot: {1,9},{3,3},{7,7}
    If that doesn't work, you'll need to do the same thing with 8s and stop incrementing as soon as the result goes over 900,000, and so on in that order until all humans are eaten.

Post a Comment

Your email is never published nor shared.

Switch to our mobile site