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 &gt;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(&quot;Enter no. of digits in multipliers : &quot;)
digits = int(digits_str)

min_plier = (10 ** (digits-1))   # Minimum n-digit   number for eg. if digits = 3, min_plier = 100
max_plier = int((&quot;9&quot; * (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(&quot;Largest palindrome is : &quot; + 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.202920s
No. of digits : 5, Largest palindrome : 9966006699, Time required for execution :  1hr 3min 54.552400s
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 &lt; 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 &lt; 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