## Project Euler 4: Find the largest palindrome product

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

A brutish way to find the largest palindrome product of two 3-digit numbers is by searching odd factors downwards from 999. We test each product as a palindrome and save it. Our search ends when the next product falls below the largest palindrome found and is less than our limit, *L*.

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

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 increment `j`

by 1.

This method could be easily extended for other even and odd length products for larger investigations.

The two factors are printed along with their product. *L* was added to solve the HackerRank version of Project Euler 4.

#### Project Euler 4 Solution

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

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

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

4 | 9999 | 9901 | 99000099 | 650 |

5 | 99979 | 99681 | 9966006699 | 55,655 |

6 | 999999 | 999001 | 999000000999 | 62,750 |

7 | 9997647 | 9998017 | 99956644665999 | 34,554,539 |

8 | 99999999 | 99990001 | 9999000000009999 | 6,252,500 |

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 quickly becoming impractical for a larger number of digits.

*Project Euler 4 Solution last updated*

I have some optimizations and several of the higher digit solutions posted on reddit.

http://www.reddit.com/r/projecteuler/comments/2c3ic8/going_further_with_004/