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

Question

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

Answer 1

• 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

Answer 2

You want to generate palindromes, and then check if they are divisible.

You want to choose a good max size \$99 * 99 = 9801\$, \$999 * 999 = 998001\$, etc. Since 9889 is larger than 9801, we know that we can use \$10 ^ \text{size} - 2\$. This is as 9779 is the largest palindrome below 9801. From this palindrome we work down to 1001. To get this range we can use range(10 ** size - 2, 10 ** (size - 1), -1).

From this we want to check that the number is actually divisible, so to optimize large numbers we can work from \$10 ^ \text{size}\$ down to \$\sqrt{\text{palindrome}}\$. The first number that is divisible is the best. And so we return the palindrome.

This algorithm is \$O(n^2)\$. Where n is \$10^\text{size}\$. But doesn't work with an input of 1. But can find the answer to the size of 7 in a couple of seconds. The code can be:

def largest_product_two(size):
    start = 10 ** size - 1
    for i in range(10 ** size - 3, 10 ** (size - 1) - 1, -1):
        palindrome = int(str(i) + str(i)[::-1])
        for j in range(start, int(palindrome ** 0.5) - 1, -1):
            if not palindrome % j:
                return palindrome

Answer 3

There is a significant algorithmic improvement for even \$n\$. We start by generalising a pattern in the values you've found for \$n=2\$ and \$n=4\$. Let \$n = 2d\$. Then \$(10^{2d} - 10^d + 1) (10^{2d} - 1) = (10^{3d} + 1)(10^d - 1)\$ is a palindrome and a product of two \$n\$-digit numbers.

Suppose \$ab\$ is a larger palindrome, where \$10^{n-1} \le a \le b < 10^n\$. Clearly we require \$a > 10^{2d}-10^d+1\$; let's rewrite as \$a = 10^{2d} - 10^d + x\$, \$b = 10^{2d} - 10^d + y\$ with \$1 < x \le y < 10^d\$. Observe that since \$ab\$ is greater than our known palindrome, its first \$d\$ digits are \$9\$, and since it's a palindrome that means that its last \$d\$ digits are \$9\$. Therefore we have \$xy = -1 \pmod{10^d}\$.

It follows immediately

1. That \$\gcd(x, 10) = 1\$, so \$x\$ is odd and not divisible by \$5\$.
2. Given such an \$x\$ we can recover \$y\$ by a division modulo \$10^d\$.

Therefore we can build a very short list of candidates by enumerating range(3, 10**(n//2), 2), skipping the terms divisible by 5, performing the extended Euclidean algorithm for the rest, and testing every pair for which we get y >= x.

Answer 4

Do you really need to print out sys.version? I really see no reason why you need to do this. Remove:

import sys
print(sys.version)

Just do this:

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

In one line:

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

Remove the semicolon:

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

(There are some other PEP8 violations in your code)

This actually doesn't avoid repetitive calculations, it does nothing:

max_plier = z          # To avoide repetitive calcualtions.

Once you have created a range object it is immutable, changing maxplier won't change the range. Just be sure to replace max_plier in your inner loop with z.

Again:

global pallindromes

Is unneeded get rid of it entirely.

I would abstract this into a function is_palindrome:

if (str(product) == str(product)[::-1]) :
    pallindromes.append(product)

Hmmm, interestingly enough I would have suggested doing a more "arithmetic" approach to determining if a number is a palindrome, this answer seems to suggest that indeed your solution is the fastest. But this isn't necessarily true for every language, be sure to profile stuff! (Well, it looks like you did so good job!)

Answer 5

This seems a bit too complicated to get 999 when entering 3, 9999, when entering 4, ...

max_plier = int(("9" * (digits+1))[:digits])

It is sufficient to do:

max_plier = int("9" * digits)

Also note that in Python ; at the end of the line are completely superfluous and their use is therefore frowned upon. Even though they are perfectly legal Python.

You keep track of the whole list of palindromes, only to calculate the max at the end. This will consume a lot of memory, especially when the numbers get bigger. Just keep track of a running maximum instead. There is also no need for the global keyword, since your whole code is in the same scope.

You can let the inner loop just run from z, instead of setting max_plier = z.

I would use str.format to display the final result.

I would add a function is_palindrome, as @Dair already suggested in his answer. This saves you one call to str as well.

Final code:

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.
'''

def is_palindrome(number_str)::
    return number_str == number_str[::-1]

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

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

# Calculate product and get palindrome
max_palindrome = 0
for z in range (max_plier, min_plier , -1):
    for x in range(z, min_plier, -1):
        product = z * x
        # Check if product obtained is palindrome and is greater than previously obtained palindrome.
        if is_palindrom(str(product)):
            max_palindrome = max(max_palindrome, product)
print("Largest palindrome is: {}".format(max_palindrome))

There also seems to be a bug in your looping. You never check x * min_plier, because of the way the for loop works. You could iterate up to min_plier - 1. Or you note that that number will never be a palindrome anyways (it starts with a 1 and ends with a 0), and realize that it is not a real bug.

Answer 6

Look at the fifth answer: 9966006699. If this is the product of two five digit numbers, then each factor must be at least 99661 (because 99660 x 99999 is too small). You would have found that solution if you had checked all products of two numbers from 99661 to 99999. That's about \$340^2\$ instead of \$100000^2\$ products to test, about 0.001%.

I'd try products a * b, where a ≤ b ≤ 99,999. Start with a = 99,999 and go down to a = 99,998, 99,997 etc. Once you have found a solution, here: 9,966,006,699, then for the next a you can find out how large b has to be at least to create a product ≥ 9,966,006,699. And you are done when you find that b ≥ 100,000 is needed.