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