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:
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:
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