Largest palindrome product from projecteuler.net

Posted by: Rod Morison 5 years, 10 months ago

(0 comments)

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
                all_fills.add((bag1, bag2))
                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[0] 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
                all_fills.add((bag1, bag2))
                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([2], 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_[0] is None or max_[0]*max_[1] < 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[0] 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[0], f[1], f[0]*f[1] if f[0] 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[0], f[1], f[0]*f[1] if f[0] 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

Comments

  • There are currently no comments

New Comment

required
required (not published)
optional