Project Euler 40

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

Q40.
1から順に順に並べて作った小数の小数第n位をdnと書いたときに、d1 * d10 * … * d1000000

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


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桁、となる。10n-1までなら、((9n-1)10n+1)/9桁となる。これで、dnが何桁の数を並べているところかがわかる。


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))))