project euler problem 26

フェルマーの小定理をみると
mod a^(p-1) p == 1 (pは2,5以外の素数）
aを１０とすると　10^(p-1)は　p-1桁のなかに循環少数が含まれている
また、余りが1になったとき循環が終わることがわかる

http://www.math.kindai.ac.jp/~chinen/junkan_f/junkan.html

ということで割り算の筆算を実装して余りが１になったときに循環しているとやればOK

import Data.List
import Data.Ord
main = print $ maximumBy (comparing (length.recurringCycle)) $ drop 3 $ takeWhile (<1000) primes

recurringCycle n = rc 1 n
    where rc n d
              | mod (n*10) d == 1 = [div (n*10) d] --余りが1のとき循環終了                          
              | otherwise = (div (n*10) d):(rc (mod (n*10) d) d )

primes = 2:[x|x<-[3,5..],isPrime x]
    where isPrime x = all ((/=0).(mod x)) $ takeWhile (<= (floor.sqrt.fromIntegral) x) primes

maximumBy で comparingをやるのをわすれてて苦労した。