Problem40

30分プログラム、その313。Problem40 - Project Euler。

正の整数を順に連結して得られる以下の10進の無理数を考える:

0.123456789101112131415161718192021...

小数点第12位は1である.
d_nで小数点第n位の数を表す. d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000 を求めよ.

使い方

*Main> solve
210

解法

1桁の数字は、1〜9なので:
(0 < k < 10)

2桁の数字は、10〜99。そして、2桁になるのはk=10からなので:
(10 <= k < 190)

同様に、3桁の数字は100〜999。そして、2桁になるのはk=190からなので:
(190 <= k < 2890)

これを一般化すると:

ここでnは

となる最小のn。

ソースコード

import Data.List

--- d(k)が何桁の数字になるか調べる

-- n桁の数字の範囲
digits :: [Int]
digits = 0 : (scanl1 (\ x y -> x + y) $ map digit [1..])
    where digit n = 9 * 10^(n-1) * n

-- d(k)が何桁か
findN k = findIndex (k <=) digits

d :: Int -> Int
d k = read $ [show d_k !! m]
    where Just n = findN k
          prev   = digits !! (n-1) + 1
          d_k    = (k - prev) `div` n + 10^(n-1)
          m      = (k-prev) `mod` n

solve = product $ take 7 $ map d [10^n | n <-[0..]]

参考

• 過去の30分プログラム
• Problem 40 - PukiWiki