Project Euler Problem 004

http://projecteuler.net/index.php?section=problems&id=4

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 is_palindromic_number(n):
    return str(n) == str(n)[::-1]

こんな感じでもOKだけど、これは回文数というよりは回文のチェックなので

def is_palindromic_number(n):
    def reverse(n):
        result = 0
        while n:
            result = result * 10 + n % 10
            n /= 10
        return result
    return n == reverse(n)

こういう感じの方が良いのかな？

問題の回文数のための3桁の2つの数の見つけ方はよく分からなかったので、Greedyに探した。

def is_palindromic_number(n):
    def reverse(n):
        result = 0
        while n:
            result = result * 10 + n % 10
            n /= 10
        return result
    return n == reverse(n)


result = 0
for i in xrange(999, 100, -1):    
    for j in xrange(i, 100, -1):
        x = i * j
        if result > x: break
        cnt += 1
        
        if is_palindromic_number(x):
            result = x
            print (i, j, x)
            
print result

答え: 993 * 913 = 906609

より良い方法

解説を見ると、Greedyで探すので正解のようだけど、問題で聞かれている回文数は6桁の数字となり、6桁の回文数は11の倍数になるので11の倍数になるようにチェックすれば良いとのこと、その方法だと調査する数が1/8くらいになる。なるほど。