５７問目

http://projecteuler.net/index.php?section=problems&id=57
√2は以下のように連分数展開できる。
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
これを1000回繰り返したとき、分子の桁数が分母より大きいものはいくつあるか求める。
分子と分母の漸化式を求めて、数えました。

main = print $ euler057 1000

euler057 :: Int -> Int
euler057 m = length $ filter diff $ take m fracs
    where diff (n, d) = (length $ show n) > (length $ show d)

fracs :: [(Integer, Integer)]
fracs = iterate next (3, 2)
    where next (n, d) = (n + 2 * d, n + d)