Just for fun over Thanksgiving, played with https://projecteuler.net/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.
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
New Comment