みをつくしのひとりよがり

2022/08/10にブログ名を変えました.仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

チャンパーノウン定数~Project Euler Problem 40~

以前,三角形の問題を扱った Project Eulerの問題です.計算量が多いですが,群数列が考え方のメインになる(数列の和計算もあるョ的な)問題です.

問題

元の問題はこちら.
Problem 40 - Project Euler

正の整数を順に連結して得られる以下の 10進の無理数を考える.
  0.12345678910\color{red}{1}112131415161718192021  \cdots

たとえば,小数第12位(赤字)は 1である. d_nで小数第  n位の数を表す.
 d_1 \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000}を求めよ.

「なんで小数にしてるの?」と思うかもしれませんが,小さい順に右へ並べるには小数の方が都合がいいんですよね.
群数列の問題では,与えられた数列を「群に分けて」「その群の特徴をつかみ」「もとの数列と個数の数列を探っていく」という方針がよくあるパターンです.
miwotukusi.hatenablog.jp

いまの問題では,

  1. 1~9,10~99,100~999,…のように「kケタの数ごとに」群を作り,
  2. 小数第 n位がどの群(第 k群=kケタの数の群)に属するかを調べ,
  3. さらに,小数第 n位がその kケタの数の中の「どの数の何ケタ目」になっているのかを調べる.

という手順をとります.
「もとの数列」が各ケタの数字になっているというのが,いつもとは違うところです.

Step1:「kケタの数」の群

kケタの数にどのような数が含まれているかを考えると,
kケタの数には 10^{k-1}から  10^k-1までの
 (10^k-1)-10^{k-1}+1 = 10^k-10^{k-1}個の数が含まれていることがわかります.

そして,kケタの数だけを並べてできる数の総ケタ数は,
  k \cdot \left( 10^k - 10^{k-1} \right)

となります.

対数の問題でも出てくる「ケタ数」ですが,以前にも書いているように具体的な数を一度考えてみればいいと思います.

  • 2ケタの数だったら  10から  99=10^2-1まで,
  • 3ケタの数であれば  100=10^2から  999=10^3-1まで

というようにです.
これで「各群でのケタ数」がわかったので,それを足し合わせれば,
1から mケタの最後の数までを並べたときの総ケタ数が
  \displaystyle{ S_m = \sum_{k=1}^m k \cdot \left( 10^k - 10^{k-1} \right) = 9 \cdot \sum_{k=1}^m k \cdot 10^{k-1} }

で与えられます.
この数列の和は,一般項が(等差数列)×(等比数列)の形となるものの総和となるので, \displaystyle{ T_m \equiv \sum_{k=1}^m k \cdot 10^{k-1} }と一度置いて, T_m - 10 \cdot T_mを計算することで,
  \begin{align} T_m - 10 \cdot T_m &= 10^0 + 10^1 + 10^2 + \cdots + 10^{m-1} - m \cdot 10^m \\ -9 \cdot T_m &= \frac{1 \cdot (10^m-1)}{10-1} - m \cdot 10^m \\ 9 \cdot T_m &= m \cdot 10^m - \frac{10^m-1}{9} \\ 9 \cdot T_m &= m \cdot 10^m - \underbrace{111 \cdots 11}_{1が m個} \end{align}

ちょうど  9 \cdot T_m = S_mとなっているので,右辺が  S_mを表しています.

Step2:小数第 n位がどの群(第 k群=kケタの数の群)に属するかを調べる

それぞれの  S_mを計算すると,
  S_1=9, \ S_2=189, \ S_3=2889, \ S_4=38889, \ S_5=488889, \ S_6=5888889

となり,

  •  d_1は第 1群(1ケタの数の中)
  •  d_{10}, d_{100}は第 2群(2ケタの数の中)
  •  d_{1000}は第 3群(3ケタの数の中)
  •  d_{10000}は第 4群(4ケタの数の中)
  •  d_{100000}は第 5群(5ケタの数の中)
  •  d_{1000000}は第 6群(6ケタの数の中)

に含まれていることがわかります.

Step3:小数第 n位の数を求める.

たとえば  d_{10000}を求めるのであれば,

  •  10000 - 2889=7111より,小数第 10000位は第 4群の第7111番目の数になっています.
  • この間 4ケタの数が並んでいるので, 7111 \div 4 = 1777...3より,1778番目の数の上位から 3ケタ目が求める数となります.
  • 4ケタの数のスタートは 1000なので,2777の 3ケタ目である「7」が  d_{10000}となります.

同様にすれば, d_1=1, \ d_{10}=1, \ d_{100}=5, \ d_{1000}=3, \ d_{10000}=7, \ d_{100000}=2, \ d_{1000000}=1となり,答えは  210となります.


「一般項が(等差数列)×(等比数列)の形となるものの総和」を求めるなんてのは入試数学ではよく出てくる内容ですが,その内容に筋道立てて落とし込めるかがポイントになりますね.
プログラムで求めるのであれば,

  • 上で書いたように,ターゲットとなるケタがどこにあるかを探す方針.
  • 逆に,付け加える数のカウンターとケタ数のカウンターを用意してカウントアップしていく(とにかく数字をターゲットのケタまで出していく)

のような感じになると思います.