Problem 64

漸化式を導き出すのに苦労した。あとは、無限小数のときと同じ手法で。

import Data.List
next n (_,(b,c)) =
let c' = (n-b*b) `div` c
n' = floor.sqrt.fromIntegral$n
(a,r) = (n'+b)`divMod`c'
in (a,(n'-r,c'))
expand n = expand' [] . iterate (next n) $ (n',(n',1))
where n' = floor.sqrt.fromIntegral$n
expand' xs (y:ys)
| elem y xs = let (a,b) = span (/=y) xs
in (map fst a,map fst b)
| otherwise = expand' (xs++[y]) ys
p064 =length.filter (odd.length.snd.expand)$[2..9999]  map (^2) [1..100]
main = print p064