Euler Project — Largest Palindrome Product
In this blog, I go though the approach I’ve taken to solve the Largest Palindrome Product problem from Project Euler.
The problem description defines a palindromic number as any positive integer that reads the same backwards as forwards. It also provides an example of the largest palindromic number — 9009, made from the product of two 2-digit numbers, 91 and 99. Finally, the problem statement asks for the largest palindromic number made from the product of two 3-digit numbers.
To tackle this problem, I decide to check if every product is palindromic. However, it’s important to narrow down the candidate numbers to a feasible searching range to minimize computation. More specifically, since the possible range of product would only be from 900² to 999².
Next, since the question is asking for the largest palindrome, it would make sense to search backwards starting from the largest product (999²).
With these things in mind, I then divide the problem into 2 parts. The first part produces a list of all palindromic numbers within the search range I mentioned above. This can be done by inverting the sequence of a number’s string form, which I described in my other blog post below:
The second part then loops through these numbers from the largest to the smallest, and determines if the number has a 3-digit integer divisor and a 3-digit integer quotient. The detailed operation is listed below:
1. for each palindrome, I create another loop that runs through all 3-digit numbers from 999 to 900.
2. for each 3-digit number, I divide from the current palindromic number to get a quotient.
3. I then check if this quotient is an integer and it contains 3 digits. If this condition is met, the current palindrome would be the largest palindromic number made from the product of two 3-digit numbers. Otherwise, step 2 is performed on the remaining palindromes until the condition is satisfied.
This idea is illustrated in the snippets below:
The complete implementation can be found the notebook below.
