Project Euler 145

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


題意どおりに書くと、数時間かかりそうです。

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

def reverse(n):
    return reduce(lambda x, y: x * 10 + y, digits(n))

def is_reversible(n):
    return n % 10 != 0 and all(d % 2 == 1 for d in digits(n + reverse(n)))

N = 10 ** 9
print sum(1 for n in xrange(1, N) if is_reversible(n))

加算するときに各桁で繰り上がり有/無で分けて考えましょう。
まず、最後の桁が無のとき、ずっと無なら各桁の和が奇数ならOKです。しかし、桁数が奇数のときは真ん中の桁の和が必ず偶数になってしまうのでNGです。偶数桁なら、最初と最後の桁は0が使えないので、和が3になるときは1+2、2+1の2通り、5なら4通り、などとなって計20通りになります。他の桁では0が使えるので、和が1になら2通り、9なら10通りで、計30通りになります。
どこかで有になるとき、それまでの桁は和が奇数です。その反対側の上位の桁では、その有の次の桁が無になります。しかしその桁の計算では奇数になりますが、繰り上がりがあって奇数になってしまいます。

無…無有…有無…無
奇…偶奇…奇奇…奇

よって、最後の桁が無なら全て無でなければなりません。
最後の桁が有のとき、次の桁が有だと、頭の桁は繰り上がりで偶数となります。

 有有…有有
1偶……奇奇

よって次の桁は無です。その次の桁が無だとすると、

 有無無…無無有
1奇偶……奇奇奇

次の桁は有になります。こうして、有で始まったら、無有を繰り返すことになります。桁数は奇数ということになります。ただし、4k+1型だと中央の桁が有になり下からの繰り上がりがないので和が偶数になってしまいNGです。4k+1型ならOKです。先ほどと同じように各桁の場合の数が決まり、桁数が与えられれば場合の数が得られることになります。その和を取ればよいでしょう。本当はべき乗の和を使えば一発ですが、そこまでする必要もないでしょう。

def N(n):
    q, r = divmod(n, 4)
    if r == 0:
        return 20 * 30 ** (2 * q - 1)
    elif r == 1:
        return 0
    elif r == 2:
        return 20 * 30 ** (2 * q)
    else:
        return 100 * 500 ** q

E = 9
print sum(N(n) for n in xrange(1, E + 1))