Problem 129

http://projecteuler.net/index.php?section=problems&id=129

これも前に考えたことがある。

111…1 = n*mとする(n<m,n/=1)。

両辺に９をかけます

999…9 = (9*n)*m

そして

1/(9*n) = m/999…9

ここで右辺を少数で表現しようとするとmが循環する。

循環列の長さは9の個数に一致。

これを利用した。

しっかりとした証明は、眠いのでパス。

{-# OPTIONS_GHC -XBangPatterns #-}
import Data.List
count n (q,r) !k | gcd 10 n /= 1 = 
| (q,r)==(,10) = k
| otherwise = count n (divMod (10*r) (9*n))$ k+1
main = print.find((>10^6).count')$[10^6..]
where count' n = count n (,100) 1

!mで正格に評価するのがポイント（だと思っている）。

mだとスタックオーバーフロー