Project Euler 4(1)

Problem 4
回文数はどちらから読んでも同じ数のことである。2桁の数字同士の積で最も大きい回文数は、9009 = 91 × 99。
3桁の整数同士の積で最も大きい回文数を求めよ。
http://projecteuler.net/index.php?section=problems&id=4

回文数の判定は、1桁ごとにバラして前後を比較します。
問題文の通り、3桁同士の積を次々と求めて、そのうち回文数で最も大きいものを得ます。


from itertools import product

def gen_digits(n):
while n:
yield n % 10
n /= 10

def is_palindromic(n):
digits = [ d for d in gen_digits(n) ]
for i in range(len(digits) / 2):
if digits[i] != digits[-i-1]:
return False
return True

def gen_palindrome():
for x, y in product(xrange(10 ** (N - 1), 10 ** N), repeat = 2):
n = x * y
if is_palindromic(n):
yield n

N = 3
print reduce(max, gen_palindrome())

しかし、これは遅いです。なんとか速くしましょう。
回文数は、6桁の場合、

105a + 104b + 103c + 102c + 101b + a = 100001a + 10010b + 1100c

だから、まず100001で割って商が1〜9になります。余りを10で割って、1001で割って商が1〜9になります。最後に余りを10で割って、11で割り切れます。これをコードにしましょう。


def is_palindromic(n):
if n >= M:
ary_d = a
else:
ary_d = b

for d in ary_d:
q = n / d
if q >= 10:
return False
n -= q * d
if n % 10:
return False
n /= 10
return n == 0

a = [ 10 ** (N * 2 - 1 - k * 2) + 1 for k in range(N) ]
b = [ 10 ** (N * 2 - 2 - k * 2) + 1 for k in range(N - 1) ]

これで4倍くらい速くなりました。
ところで、最大の数を求める問題なので、本当は大きい積から順に調べて、見つかったら打ち切ればいいはずです。これはどう実現すればいいでしょう。
こんなのはどうでしょうか。2桁で考えて、まず9800〜9899の範囲を考えます。99の倍数だと、9801がこの範囲に入ります。98は範囲に入りません。よって、9801だけ回文数の判定をします。次に、9700 〜 9799の範囲を考えます。99の倍数なら9702、98の倍数も9702ですが、乗数が99なので重複します。なので、9702を判定します。


99 98 97 …
9800 〜 9899 9801
9700 〜 9799 9702
9600 〜 9699 9603 9604

これでグッと速くなりました。
ちなみに、4桁同士の掛け算なら99000099、5桁なら9966006699、6桁なら999000000999となりました。



def is_palindromic(n):
if n >= M:
ary_d = a
else:
ary_d = b

for d in ary_d:
q = n / d
if q >= 10:
return False
n -= q * d
if n % 10:
return False
n /= 10
return n == 0

def gen_palindrome(s, e):
for x in xrange(L - 1, 0, -1):
ey = (e - 1) / x
if ey > x:
break
sy = s / x
for y in range(sy, ey + 1):
n = x * y
if is_palindromic(n):
yield n

N = 3
M = 10 ** (N * 2 - 1)
L = 10 ** N
a = [ 10 ** (N * 2 - 1 - k * 2) + 1 for k in range(N) ]
b = [ 10 ** (N * 2 - 2 - k * 2) + 1 for k in range(N - 1) ]
for s in xrange(10 ** N - 2, 0, -1):
n = reduce(max, gen_palindrome(s * L, s * L + L), 0)
if n != 0:
print n
break