- #1
mslate
- 2
- 0
I'm doing the http://projecteuler.net/" problems for garbages and giggles, and was working on problem 4 which requires finding the largest number palindrome (e.g. 10301, 54345) that is the product of two 3-digit numbers.
Below is my code, and I'm pretty sure Python will reproduce the error that I'm getting if you try it. I'm using recursion to search backwards from the product of 999 x 999, stopping at 100 x 100. I'm not very familiar with Python or programming, but I suspect that the problem's arising from the recursive calls spinning out of control and taking up too much memory. Any ideas?
Below is my code, and I'm pretty sure Python will reproduce the error that I'm getting if you try it. I'm using recursion to search backwards from the product of 999 x 999, stopping at 100 x 100. I'm not very familiar with Python or programming, but I suspect that the problem's arising from the recursive calls spinning out of control and taking up too much memory. Any ideas?
Code:
# Project Euler no. 4
# Find the largest palindrome made from the product of two 3-digit numbers
def checkPalindrome(num1,num2):
prod=str(num1*num2)
i=0
l=len(prod)
print num1, num2
# prevents infinite loop by stopping recursion beyond checking 3-digit numbers
if (len(str(num1))!=3 | len(str(num2))!=3):
return 0,0
# even
if l%2==0:
while (1):
if prod[i]!=prod[-i-1]:
a1,b1=checkPalindrome(num1,num2-1)
prod1=a1*b1
a2,b2=checkPalindrome(num1-1,num2-1)
prod2=a2*b2
return (a1,b1) if prod1 > prod2 else (a2,b2)
if i==l/2: # checked palindrome w/o error--is a palindrome
return num1, num2
i+=1
else: #odd
while (1):
if prod[i]!=prod[-i-1]:
a1,b1 = checkPalindrome(num1,num2-1)
prod1 = a1 * b1
a2,b2 = checkPalindrome(num1-1,num2-1)
prod2 = a2 * b2
return (a1,b1) if prod1 > prod2 else (a2,b2)
if i > l/2: # checked palindrome w/o error--is a palindrome
return num1, num2
i+=1
return 0,0
if __name__=="__main__":
a=999
b=999
print "Checking palindrome for 3-digit products..."
num1,num2=checkPalindrome(a,b)
print "The largest palindrome made from the product of two 3-digit" \
" numbers is %d and results from the product of " \
"%d and %d" % num1*num2, num1, num2
Last edited by a moderator: