7
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Have in mind that whenever a product or combination or permutation is mentioned, you first check itertools which is pretty optimized for that kind of operations. \$\endgroup\$ – Grajdeanu Alex. Oct 27 '16 at 10:15
  • \$\begingroup\$ int(("9" * (digits+1))[:digits]); makes little sense. Use the same method as for the previous value: (10**digits)-1 \$\endgroup\$ – njzk2 Oct 27 '16 at 14:02
7
\$\begingroup\$
  • 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

\$\endgroup\$
  • \$\begingroup\$ Although I think the step -2 is correct, I don't think it's justified when digits is odd. I've spent some time thinking about how to prove that the solution always starts and ends with 9, but I haven't yet managed it. (On the other hand, if that assumption is valid then each of 1, 3, 7, and 9 as a final digit has only one corresponding final digit which it multiplies by to give 9, so with careful choice of the starting point the inner loop could use a step of -10). \$\endgroup\$ – Peter Taylor Oct 27 '16 at 22:02
  • \$\begingroup\$ Your earlier solution had z instead of max_plier in 2nd for loop. I think that avoided repetitive calculations. So if z=999 and x = 999 , 999×999 then 999×998 and so on will be calculated. For next iteration of outer loop, z =998 and x = 998(instead of max-plier which is 999) so calculations will start from 998×998 instead of 998×999. Should max_plier be replaced by z as in your earlier edit? \$\endgroup\$ – Amey Dahale Oct 28 '16 at 4:04
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ For size 2 would it work? \$\endgroup\$ – noman pouigt Oct 27 '16 at 14:16
  • \$\begingroup\$ @nomanpouigt Yes, for size 2+ it works. largest_product_two(2) -> 9009. \$\endgroup\$ – Peilonrayz Oct 27 '16 at 14:19
  • \$\begingroup\$ Also won't it be better to just check if the palindrome can be factorized instead of dividing till the square root of the palindrome? \$\endgroup\$ – noman pouigt Oct 27 '16 at 14:20
  • \$\begingroup\$ @nomanpouigt My code isn't dividing, it's using modulo, to check if there is a factor in that range. \$\endgroup\$ – Peilonrayz Oct 27 '16 at 14:24
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!)

\$\endgroup\$
  • \$\begingroup\$ Thanks. max_plier should be reassigned inside loop. I totally missed it. \$\endgroup\$ – Amey Dahale Oct 27 '16 at 10:33
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.