(16 votes, average: 5.00 out of 5)

## Project Euler 4: Find the largest palindrome product

#### Project Euler 4 Description

Project Euler 4: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

#### Analysis

We are tasked with finding the largest palindromic number with two 3 digit factors. One method is searching factors downwards from 999 as it is more likely to find a larger product from larger factors. We test each product as a palindrome and save it and continue until we exhaust all our potential factors.

Nanogyth’s comment below demonstrates how to speed things up significantly. It summarizes that if a six digit number is palindromic it must follow the form:

$10^5 \cdot a + 10^4 \cdot b + 10^3 \cdot c + 100 \cdot c + 10 \cdot b + a$
$100001a + 10010b + 1100c$
$11(9091a + 910b + 100c)$

Where a, b, and c are integers such that 0 < a ≤ 9, 0 ≤ b, c ≤ 9

This means that one of our target factors has to be divisible by 11 and allows us to step our search index, j, by 11 when i is divisible by 11. When i is not divisible by 11 we have to decrement j by 1.

Here’s my initial simple brute-force solution; about 0.3 seconds, but not fast enough for bigger problems.

print max(i*j for i in xrange(1000) for j in xrange(i,1000) if str(i*j)==str(i*j)[::-1])


The final solution is presented below and simply performs an exhaustive investigation of 3-digit factors starting from the biggest factors until a maximum palindrome product is found. There’s an early out condition that breaks the inside loop (j) by finding a palindrome less than the current maximum. This is allowed because palindrome products are found in descending order from the perspective of the inside loop.

One subtle optimization was to check the limit before checking if the product is a palindrome as the palindrome check is more computationally expensive. If the first condition is false the succeeding conditions are ignored.

if p < L and is_palindromic(p): x, y, pmax = i, j, p


The two factors are printed along with their product. L was added to solve the HackerRank Project Euler 4 version which keeps the search to 3 digit factors but includes a limit to the palindrome product.

This program and method
solves all test cases for
Project Euler 4 on HackerRank

#### Project Euler 4 Solution

Runs < 0.003 seconds in Python 2.7.
Use this link to get the Project Euler 4 Solution Python 2.7 source.

#### Afterthoughts

• Function is_palindromic is listed in Common Functions and Routines for Project Euler
• There are only 279 discrete 6-digit palindromes which are products of two 3-digit numbers.
• The largest palindrome for some other cases (Note: I restricted the search range to something sane):
# Digits

factor 1

factor 2

product
4

9999

9901

99000099
5

99979

99681

9966006699
6

999999

999001

999000000999
7

9997647

9998017

99956644665999
8

99999999

99990001

9999000000009999
9

999920317

999980347

999900665566009999
10

9999986701

9999996699

99999834000043899999
11

99999943851

99999996349

9999994020000204999999
12

999999000001

999999999999

999999000000000000999999
13

9999996340851

9999999993349

99999963342000024336999999

You can see that this method is becoming impractical for a larger number of digits.

Project Euler 4 Solution last updated

## Discussion

### 2 Responses to “Project Euler 4 Solution”

1. I think your comment is backwards in regard to when you step by 1 vs stepping by 11.

“This means that one of our target factors has to be divisible by 11 and allows us to step our search index, j, by 11 when i is divisible by 11. When i is not divisible by 11 we have to decrement j by 1.”

What you SHOULD have said is:

“This means that one of our target factors has to be divisible by 11 and allows us to step our search index, j, by 11 when i is not divisible by 11. When i is divisible by 11 we have to decrement j by 1.”

You can further specify that this makes sense since the starting point of j, 990 (vs. 999 for i) is the largest 3-digit number that is divisible by 11, so decrementing by 11 while starting at 990 will give you all of the 3-digit numbers that are divisible by 11, which of course is exactly what we want when i is NOT divisible by 11.

Posted by Ryan McGregor | June 1, 2020, 5:45 PM
2. I have some optimizations and several of the higher digit solutions posted on reddit.