# Largest palindrome product from projecteuler.net

###### Posted by: Rod Morison 2 years, 10 months ago

Just for fun over Thanksgiving, played with https://projecteuler.net/problem=4

# Largest palindrome product

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.

## Approach

My first thought in seeing this problem was, "Can I do better than brute forcing through 900 x 900 values?" After a bit of thought, realized it was easy to find the next palindrome <= any number:

Decrement the rightmost digit of the left half of the digits or middle digit if odd length (proof omitted.) Then "palindrome replace" the digits of the right half.

With that, easy enough to descend selectively through palendroms, like

```while True:
palen = largest_palendrome(n)
n = palen - 1
```

where

```def largest_palendrome(n):
""" find largest palendrom <= n """
```

So, we need to factor the palindrome and then try all two number products of factors looking for a pair between 100 and 999. Factoring efficiently isn't easy, but is well known. I use `sympy.factorint`, with a slow (slow, slow) fallback if sympy is not present. Then the problem becomes combining the factors into two groups in all unique ways to find all 2 number factorizations.

A 5m google didn't reveal any out of the box combinatorial algorithm to this end. Here is a simple but effective implementation that takes a number of items and sorts them in to two indistinguishable bags, with at least one item per bag and all items packed.

```def two_bag_fills(items):
""" iterable of all ways of packing items into 2 unmarked (cummutative) bags """

assert isinstance(items, list)
nitems = len(items)
all_fills = set()
for bag1_size in range(nitems-1, (nitems-1)//2, -1):
for bag1 in combinations(items, bag1_size):
bag2 = items.copy()
for item in bag1:
bag2.remove(item)
bag2 = tuple(bag2)
if (bag1, bag2) not in all_fills and (bag2, bag1) not in all_fills: # prune commutative dups
yield bag1, bag2
```

With this, easy enough to write my `two_factors_between` function and finish that loop:

```def walkdown_palendrome(n, low, high):
while True:
palen = largest_palendrome(n)
factors = two_factors_between(palen, low, high)
if factors is not None:
return factors
n = palen - 1
return None, None
```

Speed? About 100 times faster for the given inputs (using sympy's `factorint`).

```brute
993*913 = 906609
0.3564819332998013s
walkdown
913*993 = 906609
0.0052792966002016325s
```
```"""
Largest palindrome product
Problem 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.

"""

import timeit
from functools import reduce
from itertools import combinations, chain

def get_palendrome(n):
""" return the palendrom of a number based on leading digits, e.g., 123456 -> 123321, 1234567 -> 1234321 """

s = str(n)
mid = (len(s) - 1) // 2
palen = [s[i] if i <= mid else s[-(i+1)] for i in range(len(s))]
return int(''.join(palen))

def mid_place(n):
""" return 10**i where i least sig place of the left half of digits of n, middle if n has odd digits """
i = 1
for _ in range(len(str(n)) // 2):
i *= 10
return i

def largest_palendrome(n):
""" find largest palendrom <= n """
palen = get_palendrome(n)
if palen > n:
# this palen is too big, subtract 1 from least sig digit of left half of n
palen = get_palendrome(n - mid_place(n))
return palen

def is_palendrome(n):
""" return True if n is a palendrome """
s = str(n)
for i in range(len(s)//2):
if s[i] != s[-(i+1)]:
return False
return True

def two_bag_fills(items):
""" iterable of all ways of packing items into 2 unmarked (cummutative) bags """

assert isinstance(items, list)
nitems = len(items)
all_fills = set()
for bag1_size in range(nitems-1, (nitems-1)//2, -1):
for bag1 in combinations(items, bag1_size):
bag2 = items.copy()
for item in bag1:
bag2.remove(item)
bag2 = tuple(bag2)
if (bag1, bag2) not in all_fills and (bag2, bag1) not in all_fills: # prune commutative dups
yield bag1, bag2

def factor(n):
""" list of prime factors of n """
factors = []
try:
from sympy import factorint
except ImportError:
if not getattr(factor, 'warned', False):
print("sympy.factorint not found, using slow factor algo: walkdown algo will be slow!")
factor.warned = True
else:
for f, m in factorint(n).items():
factors.extend([f]*m)
return factors

for f in chain(, range(3, n//2 + 1, 2)):
while n % f == 0:
factors.append(f)
n //= f
if n == 1:
break
return factors if factors else [1, n]

def two_factors_between(n, low=100, high=999):
factors = factor(n)
for f1, f2 in two_bag_fills(factors):
m1 = reduce(lambda x,y: x*y, f1)
m2 = reduce(lambda x,y: x*y, f2)
if low <= m1 <= high and low <= m2 <= high:
return m1, m2
return None, None

##
# Brute force, look at all possible factor pairs
##
def brute_palendrome(n, low, high):
""" return factors of largest palendrom <= n that is a product of factors both between low, high"""

max_ = None, None
for f1 in range(high, low-1, -1):
for f2 in range(f1, low-1, -1):
if low*high > n:
continue
if is_palendrome(f1*f2):
if max_ is None or max_*max_ < f1*f2:
max_ = f1, f2
return max_

##
# Walk down palendromes only, find and check factors
##
def walkdown_palendrome(n, low, high):
while True:
palen = largest_palendrome(n)
factors = two_factors_between(palen, low, high)
if factors is not None:
return factors
n = palen - 1
return None, None

def test():
assert not is_palendrome(956459)
assert is_palendrome(9564659)
assert get_palendrome(123456) == 123321
assert get_palendrome(1234567) == 1234321
assert mid_place(12345) == 100
assert mid_place(123456) == 1000
assert largest_palendrome(123456) == 123321
assert largest_palendrome(1234567) == 1234321
assert largest_palendrome(123000) == 122221
assert largest_palendrome(1234000) == 1233321
assert largest_palendrome(100) == 99
assert list(two_bag_fills([1,2,2])) == [((1, 2), (2,)), ((2, 2), (1,))]
assert list(two_bag_fills([1,2,3])) == [((1, 2), (3,)), ((1, 3), (2,)), ((2, 3), (1,))]
assert list(two_bag_fills([1,2,3,4])) == [((1, 2, 3), (4,)),
((1, 2, 4), (3,)),
((1, 3, 4), (2,)),
((2, 3, 4), (1,)),
((1, 2), (3, 4)),
((1, 3), (2, 4)),
((1, 4), (2, 3)),
]
assert factor(12) == [2, 2, 3]

test()

nruns = 10

f = brute_palendrome(999*999, 100, 999)
print("brute\n\t{}*{} = {}".format(f, f, f*f if f is not None else 'none'))
print("\t{}s".format(timeit.timeit("brute_palendrome(999*999, 100, 999)", number=nruns, globals=globals())/nruns))

f = walkdown_palendrome(999*999, 100, 999)
print("walkdown\n\t{}*{} = {}".format(f, f, f*f if f is not None else 'none'))
print("\t{}s".format(timeit.timeit("walkdown_palendrome(999*999, 100, 999)", number=nruns, globals=globals())/nruns))
```
```brute
993*913 = 906609
0.3938091888005147s
walkdown
913*993 = 906609
0.003834247498889454s
```

• There are currently no comments

### New Comment

required
required (not published)
optional