Project Euler Problem #4

Today we have Problem #4: The first of many to feature palindromic numbers. A palindrome is defined as a number that reads the same from left to right and from right to left. Unless otherwise specified, the term refers to palindromes in base 10. Here is the statement of this problem:

Project Euler Problem 4: Largest Palindrome Product
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.

The most obvious way to generalize this question is to let the number of digits of each factor be the input. (Doing so reveals an interesting pattern as we will find out)

Here is the solution I found to this problem:

Solution #1: Adapting Bounds on the 3-Digit Numbers

The solution I considered is constantly bounding possibilities for the factors of this palindromic product. We know the larger 3-digit number is at most 999 and the smaller one is at least 100. In general, the larger the larger factor, the larger the product will be. Therefore, it makes sense to iterate downwards from the upper bound until we either hit the lower bound or we find a number which creates a palindrome when multiplied by the upper bound. In the second case, we can reset the lower bound to this number and then continue the process of bounding by decrementing the upper bound. This process will terminate once the upper bound becomes less than the lower bound.

Sorry if that explanation was a bit confusing. Here is an implementation of that method in Python 2.7:

'''
Author: Walker Kroubalkian
"Bounding" Approach to Project Euler Problem #4
'''

import time

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

def projectEulerProblemFour(n):
    upper = 10**n - 1
    lower = 10**(n-1)
    maxFound = 0
    while(upper>=lower):
        c = upper
        while(c>=lower):
            if(isPalindrome(upper*c)):
                lower = c
                if(upper*c>maxFound):
                    maxFound = upper*c
                break
            c-=1
        upper-=1
    return maxFound

start = time.time()
print projectEulerProblemFour(3)
print("--- %s seconds ---" % (time.time() - start))

'''
Prints

906609
--- 0.00363111495972 seconds ---

for input of n = 3
'''

Hopefully my method makes more sense with this program. One interesting fact that results from this generalization is that it appears that in general, when the problem is done with (2n)-digit numbers instead of 3 digit numbers, the maximum product is 99 . . . 9900 . . . 0099 . . . 99 where there are n 9’s on each side and 2n 0’s in the middle. A similar pattern can be observed for (2n+1) digit numbers where the product tends to have a lot of 9’s and 6’s in its base 10 representation. I have not proved either of these patterns to continue, but I have observed that they hold true for small values of n. With 4-digit numbers the answer is 99000099, with 5-digit numbers the answer is 9966006699, with 6-digit numbers the answer is 999000000999, with 7-digit numbers the answer is 99956644665999, and with 8-digit numbers the answer is 9999000000009999.

I may return to this problem eventually to determine if there is a more definite pattern to these results. That is all for today. I hope you enjoyed!