 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:

 12345678910111213141516171819202122232425262728 #!/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 | September 15, 2007 at 4:19 pm | Permalink
 123 def is_palin(num):     s = str(num)     return s == s[::-1]
2. Peter | 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. | September 15, 2007 at 7:23 pm | Permalink

Never seen Project Euler before. Thanks for posting about it. 🙂

4. | 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 | 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 | September 16, 2007 at 2:13 am | Permalink

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

7. | 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.

 123456 import timeit ... t1 = timeit.Timer('palindrome()', 'from __main__ import palindrome') print t1.timeit(20)
8. | September 11, 2008 at 8:50 am | Permalink

what's are biggest 2 3-dgits palindrome?

9. leed | 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. | 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. | March 16, 2009 at 12:46 pm | Permalink

Actually, you only perform 900 * 900 my mistake.

12. | March 16, 2009 at 12:47 pm | Permalink

actually, you only perform 900 * 900

13. Nicholas | 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.

Your email is never published nor shared.