回文数 - inamori’s diary

Project Eulerでよく出てくる回文数（palindromic number）は、32523のようにどちらから読んでも同じになる整数のことです。

回文数の生成

まず思いつくのは、例えば4桁なら10〜99を用意してそれをひっくり返して結合するという方法です。10なら01と結合して、1001です。5桁なら、同様にして、間に任意の数字を入れます。10と2と01で、10201となります。下のコードは、B進法でk桁の回文数を生成します。



def gen_digits(n, B):

    while n:

        yield n % B

        n /= B
def gen_palindromic(k, B):

    l = k / 2

    if k & 1:

        for m in xrange(B ** (l - 1), B ** l):

            for d in range(B):

                n = m * 10 + d

                yield reduce(lambda x, y: x * B + y, gen_digits(m, B), n)

    else:

        for m in xrange(B ** (l - 1), B ** l):

            yield reduce(lambda x, y: x * B + y, gen_digits(m, B), m)

もう一つは再帰的な方法です。6桁の回文数を求めるのに、4桁の回文数を求め、それを10倍して、100001の倍数を足します。ただし、この方法では途中の回文数は頭が0のものも含めます。



def gen_palindromic(k, B, l = 0):

    if l == k:

        yield 0

    elif l == k - 1:

        for d in range(B):

            yield d

    else:

        begin = 1 if l == 0 else 0

        m = B ** (k - l - 1) + 1

        for d in range(begin, B):

            for n in gen_palindromic(k, B, l + 2):

                yield n * B + d * m

14桁では下のコードのほうが8倍ほど速いという結果が出ました。
以上の方法は桁数ごとに回文数を求めていますが、Project Eulerではだいたい10のべき乗までの範囲の回文数を求めるような問題になっているので、問題ありません。

各桁の数字を配列にして対応する桁を次々に比べていけばいいですが、それより速い方法があります。
10進で考えて、12321ならまず10001で割って、商が9以下で余りが2320、余りが10の倍数を確認してそれを10で割って、232。これを繰り返します。
偶数桁の場合は、B+1で割り切れるので、この判定を先にしておくと少し速くなります。また、桁数の求め方にも工夫の余地があるでしょう。
いずれにしても、生成よりはかなり遅いです。



def num_digits(n, B):

    m = 0

    while n:

        n /= B

        m += 1

    return m
def is_palindromic(n, B):

    m = num_digits(n, B)

    if (m & 1) == 0 and n % (B + 1) != 0:

        return False

    for k in range(m, 1, -2):

        d = B ** (k - 1) + 1

        r = n % d

        if r % B != 0:

            return False

        q = n / d

        if q == B:

            return False

        n = r / B

    if m & 1:

        return n < B

    else:

        return n == 0

回文数の生成

回文数の判定