最長循環小数を求める

@fumievalさんのこのツイートに触発されてやってみました。

1/xが循環小数のとき、循環部分ができるだけ長くなるような素数xを見つけます。

longestRecurringDecimal

primes = 2:f [3,5..] where f (x:xs) = x:f [y | y <- xs, mod y x /= 0]

ones = 11:(map (\x-> x*10+1) ones)

longestRecDec m n [] = ((m*9) `div` n, n, length $ show m)
longestRecDec m n (p:ps)
   = let l=f p ones in
     if l>m then longestRecDec l p ps
            else longestRecDec m n ps
     where f x (y:ys) = if y `mod` x==0 then y
                                        else f x ys

longestRecurringDecimal n
   = longestRecDec 1 1 (takeWhile (<n) $ drop 3 primes) 

longestRecurringDecimal nが本体で、nより小さい素数で、一番循環部分が長い物を探します。
戻ってくるのは、巡回列、見つかった素数、巡回列の長さ、のタプルです。

以下実行結果のサンプル：

*Main> longestRecurringDecimal 1000
(10172939979654120040691759918616480162767039674465920651068158697863682604272634791454730417090539165818921668362156663275686673448626653102746693794506612410986775178026449643947100712105798575788402848423194303153611393692777212614445574771108850457782299084435401831129196337741607324516785350966429298067141403865717192268565615462868769074262461851475076297049847405900305188199389623601220752797558494404883011190233977619532044760935910478128179043743641912512716174974567650050864699898270600203458799593082400813835198372329603255340793489318413021363173957273652085452695829094608341810783316378433367243133265513733468972533062054933875890132248219735503560528992878942014242115971515768056968463886063072227873855544252288911495422177009155645981688708036622583926754832146490335707019328585961342828077314343845371312309257375381485249237029501525940996948118006103763987792472024415055951169888097660223804679552390640895218718209562563580874872838250254323499491353,983,982)

簡単に解説すると、1/99...9（9がm個）は循環小数として、00...01（0がm-1個の後に1）の繰り返しなるので、hという数が循環列として循環する数はh/99...9の形になります。これが1/nという形だから、nは99...9を割り切らなければいけません。そのようなできるだけ長い99...9を見つけるという問題になります。99...9=9*11...1だから、素数pについて、pが11...1を割りきるような最長な11...1を探していきます。