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

14 Followers

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