Project Euler 40

プロジェクトオイラー
http://projecteuler.net/index.php
順番に解いていくことは変わらないが、これからは、ピックアップして載せることにする。

Q40.
1から順に順に並べて作った小数の小数第n位をd_nと書いたときに、d₁ * d₁₀ * … * d_1000000

各桁を順に数字を出すジェネレータを作れば、

from itertools import count

from operator import mul
def gen():

    for n in count(1):

        for s in str(n):

            yield s
def get_item(n):

    d = 0

    g = gen()

    for i in xrange(n):

        d = g.next()

    return int(d)
print reduce(mul, map(get_item, map(lambda n: 10 ** n, range(6))))

しかし、これは効率が悪い。
1〜9で9桁、10〜99で2*9*10桁、100〜999で3*9*100桁、となる。10ⁿ-1までなら、((9n-1)10ⁿ+1)/9桁となる。これで、d_nが何桁の数を並べているところかがわかる。

from itertools import count

from operator import mul
def get_number(n):

    return ((9 * n - 1) * 10 ** n + 1) / 9
def get_digit(n):

    for i in count(1):

        if n <= get_number(i):

            return i
def get_item(n):

    d = get_digit(n)

    r = n - get_number(d - 1)

    m = 10 ** (d - 1) + (r - 1) / d

    mod = (r - 1) % d

    return int(str(m)[mod])
print reduce(mul, map(get_item, map(lambda n: 10 ** n, range(6))))