The largest palindrome made from the product of two 3-digit numbers

Question

Problem description:

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.

Palindrome:

In math, a palindrome is a number that reads the same forward and backward.

Example:

353, 787, and 2332 are examples of palindromes.

By definition, all numbers that have the same digits such as 4, 11, 55, 222, and 6666 are examples of palindromes.

Step-by-Step my code:

1- largest number of n-1 digit. For example, for n = 2, upper_limit is 99

2- One plus this number is lower limit which is product of two numbers. For example, for n = 2, lower_limit is 10.

3- calculating product of two n-digit numbers

4- calculating reverse of product to check whether it is palindrome or not

5- update new product if exist and if greater than previous one

My Solution

This is my solution for problem 4 of Project Euler using Python:

def largest_palindrome_product(n):
    '''Find Largest Palindrome Product
    '''
 
    upper_limit = (10**(n))-1 
    lower_limit = 1 + upper_limit//10  
  
    max_product = 0
    for i in range(upper_limit,lower_limit-1, -1):
     
        for j in range(i,lower_limit-1,-1):
            product = i * j
            if (product < max_product):
                break
            number = product
            reverse = 0

            while (number != 0):
                reverse = reverse * 10 + number % 10
                number =number // 10

            if (product == reverse and product > max_product):
                max_product = product

    return max_product

Answer 1

Outsource secondary calculations to helper functions. Your current code is reasonable. Its primary drawback is that the Euler-solving code is cluttered up with the details of checking for palindrome status. And that check can be done more easily in the realm of strings than integers: just check whether the number's string representation equals the reversed string.

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

An alternative to compute the bounds: some more string-based thinking. As illustrated by one comment, your approach to computing upper/lower bounds is not immediately intuitive. A different approach is to think in terms of range start and stop parameters. For example, for n = 3 we want the range to start on 999 and stop on 99. You can create those values quite easily – again, with string-based logic rather than math.

def largest_palindrome_product(n):
    start = int('9' * n)
    stop = int('9' * (n - 1))
    max_product = 0
    for i in range(start, stop, -1):
        for j in range(i, stop, -1):
            p = i * j
            if p <= max_product:
                break
            elif is_palindrome(p):
                max_product = p
    return max_product

When asking for help, express expectations in the form of automated tests. The code you are posting on CodeReview is getting better – well done. However, you are still ignoring a key piece of advice given for Project Euler #1: write automated tests. Among their other benefits, such tests help your helpers, telling them precisely how to call your code (again, see the comment where there was some ambiguity on this matter), allowing them to edit your code in confidence knowing that they haven't broken anything, and providing a convenient vehicle for them to add other tests as they experiment.

def main():
    TESTS = (
        (2, 9009),
        (3, 906609),
        (4, 99000099),
        (5, 9966006699),
        (6, 999000000999),
        # You'll need a more clever algorithm to go higher.
    )
    for n, exp in TESTS:
        got = largest_palindrome_product(n)
        if got == exp:
            print('ok')
        else:
            print('GOT', got, 'EXP', exp)

if __name__ == '__main__':
    main()

Answer 2

Style Guide for Python Code

A few PEP 8 items:

• parenthesis are unnecessary in (10**(n))-1; write 10 ** n - 1
• use a space around binary operators: upper_limit // 10 instead of upper_limit//10
• use a space after commas: range(upper_limit, lower_limit - 1, -1)
• parenthesis are unnecessary around if expressions. Write if product < max_product:
• parenthesis are unnecessary around while expressions. Write while number != 0:
• group logical thoughts with blank lines. number = product and reverse = 0 belongs with the while block that reverses number, not with the if statement above them.

Efficiency

The if (product < max_product): break statement prevents the following code from executing if product isn't sufficiently large. Afterwards you also test product > max_product before setting the max_product. If product == max_product, you pass the first test, reverse the value, and then reject it with the second test. Why do that extra work? Include the equality in the first test and eliminate the second.

You compute lower_limit as 1 + (expression) and then only use lower_limit - 1. You could instead save the decremented value.

After you discover the product 906609, you eventually decrease i to 952 and start the j loop. You quickly determine in the first j loop iteration that 952 * 952 < 906609, and proceed to the i == 951, and then i == 950, and then i == 949, and so on. Futile. You could stop immediately when i * i < max_product.

Type Hints

Since your linked repo uses print(...) statements, it is clear you are using Python 3.x, which in turn means you should learn about type-hints. Using them can help make your code clearer.

The largest_palindrome_product(n) method expects n as an integer value. This can be indicated with : int in the parameter list. Additionally, the function returns an integer, which can be indicated with -> int.

Updated code

def largest_palindrome_product(n: int) -> int:
    '''Find Largest Palindrome Product
    '''
 
    upper_limit = 10 ** n - 1 
    lower_limit = upper_limit // 10  
  
    max_product = 0
    for i in range(upper_limit, lower_limit, -1):

        if i * i < max_product:
            break
     
        for j in range(i, lower_limit, -1):
            product = i * j
            if product <= max_product:
                break

            reverse = int(str(product)[::-1])   # Alternate way to reverse product
            if product == reverse:
                max_product = product

    return max_product

Further optimization

Now that you've solved the problem, read the overview from the Project Euler website for a factoring optimization you can do based on the math of the problem.

Answer 3

1. Your upper_limit and lower_limit variable definition is a little bit complicated because it involves integer division.

_

upper_limit = (10**(n))-1 
lower_limit = 1 + upper_limit//10

Much more easier for the reader is something like

lower_limit = 10**(n-1)
upper_limit = (10**n)-1

or

lower_limit = 10**(n-1)
upper_limit = 10*lower_limit-1

(forgive me not using blanks between the operators of the arithmetic expressions as proposed in PEP8)

2. More descriptive variable names would be smallest_n_digit_number and largest_n_digit_number, but maybe these names are a little bit to long. But it describes exactly their content.

3. Your number reverting code is correct, but it is simpler to convert the number to a string and revert this. Some time ago I did some testing and found out that the string approach is even faster than all my arithmetical reverse routines I coded.
   But if you write your own number reverting code it makes sense to put it in a separate function. Then you can test it separately and the main function is (a little bit) easier to read.

4. I already mentioned this in another post that it would be useful if you describe the arguments of your function and the result in the docstring of your function. This is the string following the def statement. There you can note that the result of the function is 0 if no such palindrome exists.