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

Question

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

1. returning the correct answer
2. 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?

Answer 1

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.

Answer 2

The way you use ranges is not particularly pythonic, as far as I can judge. I think something like this would be preferred:

def main(n):
    start = 10**n - 1
    for i in range(start, 0, -1):
        for j in range(start, i, -1):
             if is_palindrome(str(i*j)):
                 return i, j, i*j
    return "Not found!"

I would also make is_palindrome recursive, although I am not sure it is faster

def is_palindrome(s):
    # Empty string counts as palindromic
    return not s or s[0] == s[-1] and is_palindrome(s[1:-1])

As for optimisations -- you could convert it into a list of numbers yourself, thereby skipping some error check that str() may be doing (however, as Winston Ewert has pointed out, this is unlikely to be faster). You could also try not creating a string at all like this:

from math import log

def is_palindrome(i):
    if i < 10:
        return True
    magnitude = 10**int(log(i, 10))
    remainder = i % magnitude
    leftmost = i / magnitude
    rightmost = i % 10
    return leftmost == rightmost and is_palindrome(remainder / 10)

I don't know if this is actually faster or not. You should probably get rid of the single-use variables, seeing as I am not sure they will be inlined.

Alternative non-recursive solutions:

from math import log

def is_palindrome_integer_iterative(i):
    magnitude = 10**int(log(i, 10))
    while i >= 10:
        leftmost = i / magnitude
        rightmost = i % 10
        if leftmost != rightmost:
            return False
        magnitude /= 10
        i = (i % magnitude) / 10
    return True

def is_palindrome_string_iterative(s):
     for i in range(len(s)/2):
          if s[i] != s[-(i+1)]:
               return False
     return True

These are nowhere near as elegant as the recursive one, in my opinion, but they very well may be faster. I've profiled all five six with the inputs 53435 and 57435 (takes too long on ideone, but is fine locally) and got the following results:

                        53435             57435
Original            1.48586392403     1.48521399498
String recursive    1.64582490921     0.965192079544
Integer recursive   3.38510107994     3.06183409691
Integer iterative   2.0930211544      2.07299590111
String iterative    1.47460198402     1.44726085663
Winston's version   1.31307911873     1.29281401634

Therefore, apparently, it is possible to write something a little faster to what you have, but not by a lot; profiling with a larger set of inputs is needed to really be sure, too. If false inputs are indeed significantly faster to compute with the recursive variant, you may be better off using it as most of the results are not going to be palindromes.

EDIT: I've added the function provided by Winston to the results.

EDIT2: More functions and their running times can be found here.