６４問目

http://projecteuler.net/index.php?section=problems&id=64
N ≤ 10000 に対して、Nの平方根を連分数展開したときに、循環部の長さが奇数になるものがいくつあるか求める。
漸化式を求めて無限リストを作った後は、２６問目と同じように「ウサギとカメ」のロジックで循環部の長さを求めています。

import Data.List

main = print $ euler064 10000

euler064 :: Integer -> Int
euler064 m = length $ filter (\ a -> mod (length $ cyclePart $ rems a) 2 == 1) $
    [1..m] \\ takeWhile (<= m) [ n^2 | n <- [1..] ]

cyclePart :: Eq a => [a] -> [a]
cyclePart xs = t' : (takeWhile (/= t') $ fst $ unzip ys)
    where ((t', r') : ys) = dropWhile (\ (t, r) -> t /= r) $
              zip xs $ map head $ iterate (drop 2) $ tail xs

rems :: Integer -> [(Integer, Integer)]
rems n = iterate next (1, r)
    where r = floor $ sqrt $ fromIntegral n
          next (a, b) = let a' = div (n - b ^ 2) a
                        in (a', (div (r + b) a') * a' - b)