Project Euler [Problem 40]

間が空いた

記念すべき？40到達。

問題

Champernowne's constant

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If d_n represents the nth digit of the fractional part, find the value of the following expression.

d_1 × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000}

私訳

チャンパーノウン定数

正の整数を結合した無理小数を考える :

0.123456789101112131415161718192021...

上記の通り小数第12位は 1 である。 d_n を小数第 n 位としたとき、以下の式の値を求めよ。

d_1 × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000}

解答方針

d_n の一般的な計算方法を考える必要がある。

n から考えるのは大変なので、1桁, 2桁... のグループを考える。 先頭をゼロにしたいので k = 0 から初めて第 k グループを考えると、 第 k グループには 9 × 10k 個の整数が含まれていて、それぞれの整数が k+1 桁の幅を持つから、 グループの幅は 9(k+1) × 10^k になる。 \sum_{k=0}^{m-1} 9(k+1) × 10^k \lt n \le \sum_{k=0}^{m} 9(k+1) × 10^k であれば、 d_n は第 m グループに属する。 あとは引き算して割り算すれば n が第 m グループの何番目かわかる。