# 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 """

solutions.problem4.solve()