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?

• Winston Ewert: what makes you think your code is broken for 7 digit numbers?
• Guffa: The point of the Euler Project is that you should figure out the solution yourself, not get it from a forum...
• sepp2k: @Guffa: He did, he's just asking how to make it better.
• Guffa: @sepp2k: Most questions are designes so that you easily can get the correct result for small values, the tricky part is to make it work for large numbers, and using something other than brute force so that it doesn't take ages. So, he did the easy part...
• yurisich: @Guffa is there a pattern for palindromes? I tried looking them up, but all I got was a rule that said most of the time, a palindrome / 11 will make another palindrome, and another that said summing the reverse of two numbers will eventually produce one...is there something you could share with me?

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.

• yurisich: multic = multicand; multip = multiplier. Would it be better if I changed the names to mc and mp?
• yurisich: Thanks for the 10**n bit, and pointing out the string at the top of the method. Those were leftovers form an earlier approach. Do you know of a pattern to generate palindromes mathematically?
• Winston Ewert: @Droogans, no mc and mp don't help. Use multiplier and multicand you aren't paying per letter you use in your variable name. Use full words and avoid abbreviations

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.

• Winston Ewert: Recursion in python is going to be slow. So I gotta recommend not doing that. Also str is implemented in C and is going be much faster then anything you implement in Python.
• Winston Ewert: Your comparison seems a little unfair, is_palin_orig has to convert its integer input to a string, but you've give is_palin_strrec the string version for free. Also, you could include the suggested version from my post. But some things are unclear to me: why is the recursive version faster then the iterative version? Not what I'd expect.
• Winston Ewert: I've got a couple more variations that might be of interest: pastebin.com/FPfb6DUL. Interestingly, running the benchmarks on PyPy instead of CPython produces quite different results. In particular, your recursive version is 3 times faster then any other method I've tried.
• Komi Golov: Oh, good that you saw that; I've added a link with the new functions and with all int-to-string conversion being done on the spot. That does even out the results quite a bit. I'm getting about the same difference in PyPy (0.3 against 0.11). I suspect that this is due to tail recursion optimisation, but I'm not sure.
• Elmer: Trying some of these on various lengths numbers, it seems like the shortest (admittedly dirtiest) way to do this is also significantly faster than everything else: return num_string == num_string[::-1]. The optimisation that @WinstonEwert wrote that only compares the first and latter half starts to outperform this simplest form once you hit ~100 digit numbers. Results obtained from Python2.6 (regular CPython).