Project Euler 40(2)

本当は文字をいちいちカウントする必要はありません。例えば、d1000を求めてみましょう。
1桁の数は1〜9だから、9までで9桁です。2桁の数は10〜99の90個あるので、99までで9+180=189桁です。3桁の数は100〜999の900個あるので、999までで9+180+2700=2889桁です。よって、1000桁目は3桁の数のどこかになります。(1000-189)/3 = 270…1だから、999桁目が99+270=369の最後の数字、1000桁目が370の最初の数字、すなわち3になります。


def calc_digit(n):
k = 0
m = n
while m > 0:
k += 1
m -= k * 9 * 10 ** (k - 1)

m += k * 9 * 10 ** (k - 1)
if m == 0:
return 9
p = 10 ** (k - 1) + (m - 1) / k # number
q = (m - 1) % k + 1 # position
return p / 10 ** (k - q) % 10

N = 6
print reduce(lambda x, y: x * calc_digit(10 ** y), range(N + 1), 1)