以前,三角形の問題を扱った Project Eulerの問題です.計算量が多いですが,群数列が考え方のメインになる(数列の和計算もあるョ的な)問題です.
問題
元の問題はこちら.
Problem 40 - Project Euler
正の整数を順に連結して得られる以下の 10進の無理数を考える.
たとえば,小数第12位(赤字)は 1である.で小数第 位の数を表す.
を求めよ.
「なんで小数にしてるの?」と思うかもしれませんが,小さい順に右へ並べるには小数の方が都合がいいんですよね.
群数列の問題では,与えられた数列を「群に分けて」「その群の特徴をつかみ」「もとの数列と個数の数列を探っていく」という方針がよくあるパターンです.
miwotukusi.hatenablog.jp
いまの問題では,
- 1~9,10~99,100~999,…のように「ケタの数ごとに」群を作り,
- 小数第 位がどの群(第 群=ケタの数の群)に属するかを調べ,
- さらに,小数第 位がその ケタの数の中の「どの数の何ケタ目」になっているのかを調べる.
という手順をとります.
「もとの数列」が各ケタの数字になっているというのが,いつもとは違うところです.
Step1:「ケタの数」の群
ケタの数にどのような数が含まれているかを考えると,
ケタの数には から までの
個の数が含まれていることがわかります.
そして,ケタの数だけを並べてできる数の総ケタ数は,
となります.
対数の問題でも出てくる「ケタ数」ですが,以前にも書いているように具体的な数を一度考えてみればいいと思います.
- 2ケタの数だったら から まで,
- 3ケタの数であれば から まで
というようにです.
これで「各群でのケタ数」がわかったので,それを足し合わせれば,
1から ケタの最後の数までを並べたときの総ケタ数が
で与えられます.
この数列の和は,一般項が(等差数列)×(等比数列)の形となるものの総和となるので,と一度置いて,を計算することで,
ちょうど となっているので,右辺が を表しています.
Step2:小数第 位がどの群(第 群=ケタの数の群)に属するかを調べる
それぞれの を計算すると,
となり,
- は第 1群(1ケタの数の中)
- は第 2群(2ケタの数の中)
- は第 3群(3ケタの数の中)
- は第 4群(4ケタの数の中)
- は第 5群(5ケタの数の中)
- は第 6群(6ケタの数の中)
に含まれていることがわかります.
Step3:小数第 位の数を求める.
たとえば を求めるのであれば,
- より,小数第 10000位は第 4群の第7111番目の数になっています.
- この間 4ケタの数が並んでいるので,より,1778番目の数の上位から 3ケタ目が求める数となります.
- 4ケタの数のスタートは 1000なので,2777の 3ケタ目である「7」が となります.
同様にすれば,となり,答えは となります.
「一般項が(等差数列)×(等比数列)の形となるものの総和」を求めるなんてのは入試数学ではよく出てくる内容ですが,その内容に筋道立てて落とし込めるかがポイントになりますね.
プログラムで求めるのであれば,
- 上で書いたように,ターゲットとなるケタがどこにあるかを探す方針.
- 逆に,付け加える数のカウンターとケタ数のカウンターを用意してカウントアップしていく(とにかく数字をターゲットのケタまで出していく)
のような感じになると思います.