Project Euler – Problem 4

This is the fourth post in my Project Euler series. The third problem is here.

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is [latex]9009 = 91 \cdot 99[/latex].

Find the largest palindrome made from the product of two 3-digit numbers.

I was a little disappointed at the simplicity of this problem. There’s just not really much to it. First off, we need to know how to determine if a number is a palindrome. To do this, we need to be able to calculate a number’s reverse. We can obtain the digits of a number 1 at a time by using the modulo operator. Example: [latex]17 \mod 10 = 7[/latex]. Knowing this, we simply need to remove a digit from x and put it onto y until there are no more digits on x (making sure to shift the digits on y as we go of course.

This is simple enough. As we know from the description of the problem, a palindrome is something that reads the same forward and backward. So from here it’s a pretty obvious step to know if a number is a palindrome.

From here, there’s nothing left but looping through to find the largest palindromic number. There’s not really much room for optimization, however I did find some. Assuming that you always calculate [latex]x \cdot y[/latex] then you never need to calculate [latex]y \cdot x[/latex] because multiplication is commutative. Because of this, we only need to calculate all values of [latex]x \cdot y[/latex] where [latex]x > y[/latex] and x and y are both 3 digit numbers. If we were to calculate all values of [latex]x \cdot y[/latex] including those where [latex]x < y[/latex] then we would perform roughly twice as many multiplications, something that really isn’t a big deal for such a small amount of math (but imagine if you had to solve this problem by hand.)


Leave a Comment

Your email address will not be published. Required fields are marked *