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.202920s
No. of digits : 5, Largest palindrome : 9966006699, Time required for execution : 1hr 3min 54.552400s
permutationis mentioned, you first check
itertoolswhich is pretty optimized for that kind of operations. \$\endgroup\$
int(("9" * (digits+1))[:digits]);makes little sense. Use the same method as for the previous value: