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

2

3

s = str(num)

return s == s[::-1]

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)

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

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

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

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?

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

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.

2

3

4

5

6

...

t1 = timeit.Timer('palindrome()', 'from __main__ import palindrome')

print t1.timeit(20)

what's are biggest 2 3-dgits palindrome?

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

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.

Actually, you only perform 900 * 900 my mistake.

actually, you only perform 900 * 900

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