Projects

Project Euler Problem #4 – Palindromic Numbers

Problem 4 asks us to “Find the largest palindrome made from the product of two 3-digit numbers.” First we know our maximum factor is 999, which safely puts our possible palindromes in the 6 digit range. This is important because of the proof that all even-digit palindromes have 11 as a factor. I use this to reduce the possible numbers to check.

Rather than checking all the possible products for palindrome-ness, I decided to start from the largest possible number (999*999), working backward. At each multiple of 11, the number is tested for palindrome, and if found, tested for the existence of two 3-digit factors.

In retrospect, this method required ~91k iterations to determine palindrome-ocity, and another ~82k iterations to test each palindrome’s factors’ lengths (173k total!). In comparison, a factor-first approach starting with 990 (90*11) and working backward by 11 would have only required 7 factor testing loops with a max bound of 899 possibilities each – yielding only 6293 iterations total.

And the code via codepad.org: http://codepad.org/wD9u5sHW

3 thoughts on “Project Euler Problem #4 – Palindromic Numbers”

  1. >2 Questions, Why Python and (given I don't know Python) why define BigO as a global twice?Also, to fudge it a little, I'd have calculated the end time as a variable before printing the results.

  2. >I like Python's clean and structured appearance, as well as I prefer writing small programs in an interpreted language for portability. Python wants you to be very certain of the scope of your variables, so it requires global declaration inside every function that uses the variable. Looks funny, for sure!Good point on the time calc. Those prints are very time consuming.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s