problem_004

import timeit
from primefac import isprime

"==============================================="

" 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 x 99. "

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

"==============================================="


" Solution 1"

def cheat_even(num):
    nine = '9'*(num/2)
    num1 = nine + nine
    num2 = nine + '0'*(-1 + num/2) + '1'
    product = nine + '0'*(num) + nine
    return ((int(num1), int(num2)), int(product))


def is_palindrome(n):
    """Return True if n is a palindrome, False otherwise."""
    s = str(n)
    return s == s[::-1]


def product_lst(n):
    if n % 2 == 0:
        return cheat_even(n)
    n = 10**n
    palindrome = max_palindrome = 0
    pair = (0, 0)
    for i in xrange(n - 1, 0, -1):
        # Since all palindromes are divisible by 11, either j or i has to be as well"
        if i % 11 == 0:
            j_max = i
            j_range = xrange(j_max + 1, min(palindrome/i, j_max), -1)
        else:
            j_max = 11 * int(i / 11)
            j_range = xrange(j_max, min(palindrome/i, j_max), -11)

        if j_max * i < palindrome:
            break

        for j in j_range:
            product = i * j
            if is_palindrome(product):
                if product > palindrome:
                    palindrome = product
                    pair = (i, j)
                    break
    return (pair, palindrome)


" Solution 2"

def palindrome_product(n):
    if n % 2 == 0:
        return cheat_even(n)
    en = 10 ** n
    en1 = 10 ** (n - 1)
    for p in generate_palindromes(n):
        p //= 11
        if isprime(p):
            continue
        # Generate numbers such that 11*i has length n
        for i in xrange(en // 11, max(p // en, en1 // 11), -1):
            if p % i == 0:
                return (i * 11, p // i), p * 11


def generate_palindromes(n, increase=False):
    """
    Generates palindromes of length 2n.
    Changing increase to True causes the function to yield the smallest numbers first.
    """
    en = 10 ** n
    en1 = 10 ** (n - 1)
    range_ = xrange(en1, en) if increase else xrange(en - 1, en1 - 1, -1)
    for i in range_:
        i = str(i)
        yield int(i + i[::-1])

if __name__ == '__main__':

    # n = 10
    limit = 2
    print product_lst(limit)
    for i in range(1, 8):
        print i, palindrome_product(i)

    for i in range(1, 8):
        print i, product_lst(i)