Project Euler 40（2）

本当は文字をいちいちカウントする必要はありません。例えば、d₁₀₀₀を求めてみましょう。
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)