Project Euler Problem 4: Largest Palindrome Product

The source code for this problem can be found here.

Problem Statement

A palindromic number reads the same both ways. The largest palindrome made from the product of two \(2\)-digit numbers is \(9009 = 91 \times 99\).

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

Solution Discussion

Let \(x\) be one \(3\)-digit number and let \(y\) be the other

Observe that the product of two \(3\)-digit numbers will be either a \(5\) or \(6\) -digit number. Further, if such numbers were palindromes, they could be expressed in base \(10\) in one of the following two ways:

\[\begin{split} abcba &= & 10000 \times a &+ 1000 \times b &+ 100 \times c &+ 10 \times b &+ a \\ abccba &= 100000 \times a +& 10000 \times b &+ 1000 \times c &+ 100 \times c &+ 10 \times b &+ a \\\end{split}\]

Where \(a,b,c\) are decimal digits.

Since we are looking for a maximal product, we will assume that it is a \(6\)-digit one. Observe that:

\[\begin{split}abccba &= 100000 \times a + 10000 \times b + 1000 \times c + 100 \times c + 10 \times b + a \\ &= 100001 \times a + 10010 \times b + 110 \times c \\ &= 11 \times (9091 \times a + 910 \times b + 10 \times c)\end{split}\]

Since \(11 | x \times y\) and \(11\) is prime then \(11 | x\) or \(11 | y\). Without loss of generality, assume that \(11 | y\).

To solve this problem search through all \(3\)-digit numbers \(x,y \in \mathbb{N}\) where \(11 | y\). Then, identify all palindromic products \(x \times y\). Find the maximum such \(x \times y\).

Note

if the maximal product was a \(5\)-digit number then an alternative approach would be needed.

Solution Implementation

from lib.digital import is_palindrome


def solve():
    """ Compute the answer to Project Euler's problem #4 """
    answer = 0
    for x in range(100, 1000):  # all three digit decimal numbers
        for y in range(110, 1000, 11):  # all three digit decimal numbers that are divisible by 11
            if is_palindrome(x * y):
                answer = max(answer, x * y)
    return answer


expected_answer = 906609

solutions.problem4.solve()

Compute the answer to Project Euler’s problem #4