分子が1の分数を単位分数と呼ぶ。分母が2から10の時の単位分数を少数で表し たものは次のようになる。1/2 = 0.5, 1/3 = 0.(3), 1/4 = 0.25, 1/5 = 0.2, 1/6 = 0.1(6), 1/7 = 0.(142857), 1/8 = 0.125, 1/9 = 0.(1), 1/10 = 0.1
ここで0.1(6)は0.16666666…を意味し、1桁の繰り返し周期を持つ。1/7は6桁 の繰り返し周期を持つことがわかる。
d<1000の範囲で、分数1/dを少数であらわしたとき繰り返し周期がもっとも 大きくなるdを求めよ
比較する対象は分数を少数で表したときの繰り返し周期の長さで求める解は分 数の分母なので、問題12のときと同様にその二つの値のtupleのリストを生成し、 maximumByで最大のものを求めて解を求めるという方針にする。
繰り返す部分の長さは以下のように関数recurringCycleを定義する。割り算を 筆算でやるときの要領で、現時点のあまりをnで割り、そのあまりを10倍して次 の桁の計算を行う。途中であまりが0になったら、それは割り切れるので繰り返 す部分は存在しない。そうでない場合は、現時点でのあまりをリストとして順 に渡し、ある時点でのあまりが以前のあまりと一致すればそれ以降は同じ値を 繰り返すことがわかる。一致するまでのリストの長さが繰り返し周期の長さと なる。
recurringCycle n = rec' 1 []
where rec' x l = if m == 0
then 0
else maybe (rec' (m * 10) (m : l))
(+ 1) $ findIndex (== m) l
where m = x `mod` n
euler026 = fst $ maximumBy cmpSnd [(n, recurringCycle n) | n <- [1..999]]
関数recurringCycleをパターンマッチ的な書き方で書いてみる。まずif文で判 定するかわりに関数rec’にガードを使う。次にmaybe関数を使っていたところを caseに書き換える。こっちのほうがHaskellぽいか。少なくともJustとNothing の処理は明示されてわかりやすいかな。
recurringCycle n = rec' 1 []
where rec' x l
| m == 0 = 0
| otherwise = case findIndex (== m) l of
Just i -> i + 1
Nothing -> rec' (m * 10) (m : l)
where m = x `mod` n