Project Euler 36

Problem 36
（中略）10進でも2進でも回文になる100万より小さい数の和を求めよ。
http://projecteuler.net/index.php?section=problems&id=36

どちらかの進数で回文数を生成して、それがもう一方の進数で回文になっているかを判定すればよいです。100万までということなので、10進で生成するほうがよいでしょう（コードは下）。

もう一つやり方があります。回文数の判定は時間がかかるのでそれは避けて、両方の進数で回文数を生成します。

0 1 2 3 4 5 6 7 8 9 11 22 33 ...

0 1 3 5 7 9 15 17 21 27 31 33 ...

生成された両方の回文数を見て、どちらかが小さければ小さいほうを一つ進めます。同じならば出力して、両方一つ進めます。

速度を比べてみると、上のほうが少し速いという結果になりました。ただ、コードの書き方次第では逆転するかもしれません。

# code1

from itertools import ifilter
def gen_palindromic_core(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_core(k, B, l + 2):

                yield n * B + d * m
def gen_palindromic(B, max_k):

    for k in range(1, max_k + 1):

        for n in gen_palindromic_core(k, B):

            yield n
def num_digits(n):

    if n == 0:

        return 0

    m = int(N * 3.1) + 1

    while n < 1 << m:

        m -= 1

    return m + 1
def is_palindromic(n):

    p = n

    m = num_digits(n)

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

        return False

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

        d = (1 << (k - 1)) + 1

        r = n % d

        if r & 1:

            return False

        q = n / d

        if q == 2:

            return False

        n = r >> 1

    if m & 1:

        return n < 2

    else:

        return n == 0
N = 6

print sum(ifilter(is_palindromic, gen_palindromic(10, N)))

# code2

from itertools import ifilter
def gen_palindromic_core(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_core(k, B, l + 2):

                yield n * B + d * m
def gen_palindromic(B, max_k):

    for k in range(1, max_k + 1):

        for n in gen_palindromic_core(k, B):

            yield n
def gen_both_palindromic():

    g = gen_palindromic(2, N * 4)

    m = g.next()

    for n in gen_palindromic(10, N):

        while True:

            if m >= n:

                if m == n:

                    yield n

                break

            else:

                m = g.next()
N = 6

print sum(gen_both_palindromic())