Generalized Project Euler #4: Largest palindrome from product of two n-digit numbers in Python

This solves Project Euler 4: Largest palindrome product using Python (not limited to 3 digit numbers). I need suggestions for improvements to either the Python code or the math/algorithm since time of execution increases exponentially as number of digits in multipliers increase.

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.

Here, I am trying to generalise the problem for n-digit numbers:

import sys
print(sys.version)

'''
A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009    = 91 × 99.
This program intends to find the largest palindrome made from the product of    two n-digit numbers.
'''

digits_str = input("Enter no. of digits in multipliers : ")
digits = int(digits_str)

min_plier = (10 ** (digits-1))   # Minimum n-digit   number for eg. if digits = 3, min_plier = 100
max_plier = int(("9" * (digits+1))[:digits]);   # Maximum n-digit number for eg. if digits = 3, max_plier = 999

# Calculate product and get palindrome
pallindromes = []
for z in range (max_plier, min_plier , -1):
    max_plier = z          # To avoide repetitive calcualtions.
    
    for x in range(max_plier, min_plier, -1):
        global pallindromes
        product = z * x

        # Check if product obtained is palindrome and is greater than previously obtained palindrome.
        if (str(product) == str(product)[::-1]) :
            pallindromes.append(product)

print("Largest palindrome is : " + str(max(pallindromes)))

Here's the time required for execution as the number of digits increase:

No. of digits : 2, Largest palindrome : 9009, Time required for execution : 1.403140s

No. of digits : 3, Largest palindrome : 906609, Time required for execution : 1.649165s

No. of digits : 4, Largest palindrome : 99000099, Time required for execution : 39.202

-
Instead of build a list of palindromes, calculate max palindrome.

-
When z * z is lower than max_palindrome, You can break the first for loop (all other palindromes will be lower).

-
When palindrome is lower than max_palindrome, You can break the second for loop (all other palindromes will be lower). Thanks @Peter Taylor for fix location of if statement.

-
Convert int to str is expensive. Do it once, not twice.

-
Based of @Peter Taylor algorithm, set step to -2

-
Based on Joe Wallis algorithm, modify second loop to range(max_plier, int((z * z) ** 0.5), -2)

Code:

min_plier = 10 ** (digits - 1)  # Minimum n-digit number for eg. if digits = 3, min_plier = 100
max_plier = 10 ** digits - 1    # Maximum n-digit number for eg. if digits = 3, max_plier = 999

max_palindrome = 0

for z in range(max_plier, min_plier, -2):
    if z * z < max_palindrome:
        break

    for x in range(max_plier, int((z * z) ** 0.5), -2):
        product = z * x

        # Check if product is greater than previously obtained palindrome.
        if product < max_palindrome:
            break

        sproduct = str(product)

        # Check if product obtained is palindrome.
        if sproduct == sproduct[::-1]:
            max_palindrome = product

print("Largest palindrome is : %s" % max_palindrome)

Test you solution:


No. of digits : 4, Largest palindrome : 99000099, Time required for
execution : 32s


No. of digits : 5, Largest palindrome : 9966006699, Time required for
execution : 55min

Test my solution


No. of digits : 4, Largest palindrome : 99000099, Time required for
execution : 1ms


No. of digits : 5, Largest palindrome : 9966006699, Time required for
execution : 7ms


No. of digits : 6, Largest palindrome : 999000000999, Time required for
execution : 67ms


No. of digits : 7, Largest palindrome : 99956644665999, Time required for
execution : 373ms

Final soulution and explanation

Lets look at simple example:

mmax = 4
for i in range(mmax, 1 - 1, -1):
    for j in range(mmax, i - 1, -1):
        print(i, j)

4 4

3 4

3 3

2 4

2 3

2 2

1 4

1 3

1 2

1 1

It's combinations with replacement (not permutation). In this case first palindrome is max palindrome.

digits = int(input("Enter no. of digits in multipliers : "))

def largest_product_two(digits):
    min_plier = 10 ** (digits - 1)  # Minimum n-digit number for eg. if digits = 3, min_plier = 100
    max_plier = 10 ** digits - 1    # Maximum n-digit number for eg. if digits = 3, max_plier = 999

    for z in range(max_plier, min_plier, -2):
        for x in range(max_plier, z - 1, -2):
            product = z * x
            sproduct = str(product)

            # Check if product obtained is palindrome.
            if sproduct == sproduct[::-1]:
                return product

    return None

out = largest_product_two(digits)

print("Largest palindrome is : %s" % out)

Hint to check

For size=3 palindrome is when:

\$100000x + 10000y + 1000z + 100z + 10y + x\$

\$100001x + 10100y + 1100z\$

\$11(9091x + 910y + 100z)\$

For size=4 is similar.

Palindrome is divisible by 11

for z in range(max_plier, min_plier, -2):
    for x in range(max_plier, z - 1, -2):
        product = z * x
        if product % 11 != 0:
            continue

or more pythonic

products = (z * x
            for z in range(max_plier, min_plier - 1, -2)
            for x in range(max_plier, z - 1, -2)
            if z * x % 11 == 0)
for product in products:
    sproduct = str(product)

    # Check if product obtained is palindrome.
    if sproduct == sproduct[::-1]:
        max_palindrome = product
        break

No. of digits : 6, Largest palindrome : 999000000999, Time required for
execution : 30ms


No. of digits : 7, Largest palindrome : 99956644665999, Time required for
execution : 166ms


No. of digits : 8, Largest palindrome : 9999000000009999, Time required for
execution : 51s

StackExchange Code Review Q#145396, answer score: 7