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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Michael Tang

Michael Tang

M.S. in Data Science candidate, 2022 @ Duke University | Biomedical Engineer | Workout Enthusiast