Project Euler 40（1）

Problem 40
無理数を次のように正の整数を結合して作る：
0.123456789101112131415161718192021...
小数部の12番目の数字は1である。
d_n を小数部のn番目の数字としたとき、次の値を求めよ。
d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000
http://projecteuler.net/index.php?section=problems&id=40

まず、小数部の文字列を具体的に作るという方法があります。単純に適当な大きさまでの整数を文字列にして結合します。

N = 6

s = reduce(lambda x, y: x + str(y), range(1, 10 ** N + 1), "")

しかし、これは非常に遅いです。文字列の大きいところでは、文字列の結合は結果の文字列の長さの比例以上の時間がかかるからです。この方法では、長い文字列を次々に生成することになります。
それではどうすればよいでしょうか。例えば長さ100万の文字列を50万同士の文字列の結合で生成し、50万の文字列は25万同士の文字列の結合で生成する、というようにすればよいです。こうすると、トータルでも最終的な長さに比例した時間で済むはずです。

def make_string(begin, end):

    if begin == end:

        return str(begin)

    else:

        mid = (begin + end) / 2

        return make_string(begin, mid) + make_string(mid + 1, end)
N = 6

s = make_string(1, 10 ** N)

print reduce(lambda x, y: x * int(s[10**y-1]), range(N + 1), 1)

上の方法は、半分ずつというわけではないですが、そこそこの速さで文字列を生成します。そして、ほしい数字を添え字で取り出しています。
しかし、文字列にするのは乱暴でメモリも食うので、次々に数字を出して1番目、10番目、…、100万番目を拾うというのはどうでしょう。

from itertools import count
def gen_digits():

    for n in count(1):

        for d in str(n):

            yield d
def digit(n1, n2, g):

    return int(reduce(lambda x, y: g.next(), xrange(n1, n2 + 1)))
N = 6

g = gen_digits()

print reduce(lambda x, y: x * digit(y / 10, y, g),

                    map(lambda n: 10 ** n, range(N + 1)), 1)

これで少し速くなります。
digit関数は、(n2 - n1)回gから値を出させて最後を整数にして返す関数です。少しトリッキーにreduceを使っています。