highest palindrome with 3 digit numbers in python

Question

In problem 4 from http://projecteuler.net/ it says:

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.

I have this code here

def isPalindrome(num):
    return str(num) == str(num)[::-1]
def largest(bot, top):
    for x in range(top, bot, -1):
        for y in range(top,bot, -1):
            if isPalindrome(x*y):
                return x*y
print largest(100,999)

It should find the largest palindrome, it spits out 580085 which I believe to be correct, but project euler doesn't think so, do I have something wrong here?

---

When I revered the for loop I didn't think it through, I removed the thing that checks for the biggest, silly me. Heres the working code

def isPalindrome(num):
    return str(num) == str(num)[::-1]
def largest(bot, top):
    z = 0
    for x in range(top, bot, -1):
        for y in range(top,bot, -1):
            if isPalindrome(x*y):
                if x*y > z:
                    z = x*y
    return z
print largest(100,999)

it spits out 906609

Solution 1

Iterating in reverse doesn't find the largest x*y, it finds the palindrome with the largest x. There's a larger answer than 580085; it has a smaller x but a larger y.

Solution 2

This would more efficiently be written as:

from itertools import product

def is_palindrome(num):
    return str(num) == str(num)[::-1]

multiples = ( (a, b) for a, b in product(xrange(100,999), repeat=2) if is_palindrome(a*b) )
print max(multiples, key=lambda (a,b): a*b)
# (913, 993)

You'll find itertools and generators very useful if you're doing Euler in Python.

Solution 3

Not the most efficient answer but I do like that it's compact enough to fit on one line.

print max(i*j for i in xrange(1,1000) for j in xrange(1,1000) if str(i*j) == str(i*j)[::-1])

Solution 4

Tried making it more efficient, while keeping it legible:

def is_palindrome(num):
    return str(num) == str(num)[::-1]

def fn(n):
    max_palindrome = 1
    for x in range(n,1,-1):
        for y in range(n,x-1,-1):
            if is_palindrome(x*y) and x*y > max_palindrome:
                max_palindrome = x*y
            elif x * y < max_palindrome:
                break
    return max_palindrome

print fn(999)

View more solutions

Comments

[FabianCook]

Hmm, lets change this around a bit, brb.

[japreiss]

Agreed. Rather than returning as soon as you find a palindrome, you need to test every combination and keep track of the largest.

[FabianCook]

Im only using python for this because it is an interpreted language, otherwise I would use java

[Jon Clements]

@SmartLemon fair enough - Haskell's very useful as well though ;)

[Jon Clements]

@SmartLemon For these kind of things - definitely - look at the haskell solutions on the Euler answer board for the ones you've already solved - you'll find code snippet (I think there's also a website which has the code written for the first 'n' many problems in Haskell as well)

[olyv]

Comments to clarify your code are highly appreciated

[rakvium]

The palindrome 997799 is not a product of two 3 digit numbers, it has 11 and 90709 as prime factors.

[Yannis]

It would be useful adding a few lines noting/explaining your approach.