Project Euler 26 by F#

euler26.fs

#light

(* 次のような考え方で解きました。

   割り算の筆算を考えると、小数部が循環するのは、余りが循環しているからである。
   割り算の筆算と同じ計算手順を踏みながら計算途中にあらわれる、余りをチェックして
   行けばよい。もし以前と同じ余りが出現したら、それ以降は過去と同じ計算が行われる
   ことになるので、算出される小数部は循環する。
   つまり、筆算の余りに同じものが現れるまでの計算回数が、循環小数の循環部の長さである。

   なお、割り算の余りのバリエーションは、割る数の大きさに依存する。
   n % d の答えとなり得るのは 0〜(d-1) まで。d が大きいほど循環部が長くなる可能性がある。
   例えば n % 3 は、余りのバリエーションが 0 1 2 の３つだけなので、循環部分の長さは
　　高々 3 でしかない。（何故なら４つ目は必ず既出のいずれかの値になるから）。
　　n % 997 は 0〜996 まで 997パターンの余りが出現し得る。したがって循環部分の長さは
　　高々 997 となる。
   
　　以上のことから、「n / d の循環節の長さは最大で d」という結論が導き出せる。

   この問題では、最大値を求めるので、d の値は大きいほうから降順にチェックしてゆき、
　　既出の最大循環長よりも d が小さくなったらそれ以降は計算する必要はない。
*)

// 割り算の筆算の要領で余りの無限シーケンスを生成する。
let remainders n m =
    let f n = let k = n % m in Some (k, k * 10)
    Seq.unfold f n

// シーケンス xs の先頭から要素を見て行ゆき、最初に既出の値が現れる箇所を探し、
// その値が以前に出現した位置との差を返す。
let distanceOfSameValueElements xs =
    let rec loop i dict xs =
        let x = Seq.head xs
        match Map.tryFind x dict with
        | None -> loop (i+1) (Map.add x i dict) (Seq.skip 1 xs)
        | Some j -> i - j
    loop 0 Map.empty xs

//  1 / d の循環部の長さを求める
let recurringLength = remainders 1 >> distanceOfSameValueElements

// d をデクリメントしながら recurringLength を計算しその最大値を求める。
// 既出の最大値よりも d の値が小さくなったらそこで終了。
let euler26 n =
    let rec loop d dMax lenMax =
        if lenMax >= d then
            dMax
        else
            let len = recurringLength d
            if len > lenMax then
                loop (d-1) d len
            else
                loop (d-1) dMax lenMax
    loop n 0 0

// 実行
printfn "%d" (euler26 999)