Project Euler, #4: Incorrect Results on 7-digit numbers

I've got my answer working (up until a 7-digit answer is requested, anyway), and would like some help

• returning the correct answer

• speeding up the results

I was thinking of storing the values of the possible palindromes before beginning my calculations, but I know it wouldn't speed things up anyhow. I've also read around that the 'divide by 11' trick isn't always reliable (see comment #2...900009 / 11 = 81819).

My code skims the top 10% of both the inner and outer loop before it decrements the outer loop by one, and repeats until the first result is found. This works fine, until the answer for 7-digit numbers is requested.

"""http://projecteuler.net/problem=4

Problem 4
16 November 2001

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.

"""

def main(n):
    """return the largest palindrome of products of `n` digit numbers"""
    strstart = "9" * n
    multic = int(strstart)
    multip = multic -1
    top = multic
    while multic > top * .9:
        while multip > multic * .9:
            multip -= 1
            if isPalin(multic * multip):
                return multic, multip, multic*multip
        multip = multic
        multic -= 1

def isPalin(n):
    n = str(n)
    leng = len(n)
    half = n[:leng/2]
    if n[leng/2:] == half[::-1]:
        return True
    return False   

if __name__ == '__main__':
    main(3)

How's my approach here?

def main(n):
    """return the largest palindrome of products of `n` digit numbers"""
    strstart = "9" * n
    multic = int(strstart)

Firstly, for two such short lines you'd do better to combine them. multic = int("9" * n). However, even better would be to avoid generating strings and then converting to ints. Instead, use math. multic = 10**n - 1

multip = multic -1

Guessing what multip and multic mean is kinda hard. I suggest better names.

top = multic

    while multic > top * .9:

You should almost always use for loops for counting purposes. It'll make you code easier to follow.

while multip > multic * .9:
            multip -= 1
            if isPalin(multic * multip):
                return multic, multip, multic*multip
        multip = multic
        multic -= 1

def isPalin(n):

Use underscores to seperate words (the python style guide says so) and avoid abbreviations.

n = str(n)
    leng = len(n)

This assignment doesn't really help anything. It doesn't make it clearer or shorter, so just skip it

half = n[:leng/2]
    if n[leng/2:] == half[::-1]:
        return True
    return False

Why split the slicing of the second half in two? Just do it all in the if. Also use return n[...] == half[..] no need for the if.

if __name__ == '__main__':
    main(3)

Here is my quick rehash of your code:

def main(n):
    """return the largest palindrome of products of `n` digit numbers"""
    largest = 10 ** n - 1
    for a in xrange(largest, int(.9 * largest), -1):
        for b in xrange(a, int(.9 * a), -1):
            if is_palindrome(a * b):
                return a, b, a * b

def is_palindrome(number):
    number = str(number)
    halfway = len(number) // 2
    return number[:halfway] == number[:-halfway - 1:-1]

if __name__ == '__main__':
    print main(3)

Your link on 7-digit numbers is to a post discussing integer overflow in Java. Integer overflow does not exist in Python. You simply don't need to worry about that.

The challenge asks the answer for a 3 digit problem, so I'm not sure why you are talking about 7 digits. Your code is also very quick for the 3 digits so I'm not sure why you want it faster. But if we assume for some reason that you are trying to solve the problem for 7 digits and that's why you want more speed:

My version is already a bit faster then yours. But to do better we need a more clever strategy. But I'm not aware of any here.

StackExchange Code Review Q#7615, answer score: 4