module Problem57 where

main :: IO ()
-- sqrt(2) = [1;2,2,2,...]
-- p(0) = 1, q(0)=1;
-- We know that p(n) = a(n)*p(n-1)+p(n-2) and q(n) = a(n)*q(n-1)+q(n-2)
-- [Theorem 12.9 Rosen Elementary Number Theory 5th edition]
-- here a(n)=2 for n>=1
-- (p(n), q(n)) = (1,1), (3,2), (7,5), (17,12), ..
main =
    print . length . filter (\(a, b) -> digits a > digits b) . map convergent $ [0 .. 999]
  where
    digits     = length . show
    convergent = (map convergent' [0 ..] !!)
      where
        convergent' 0 = (1, 1)
        convergent' 1 = (3, 2)
        convergent' n = (2 * p + p', 2 * q + q')
          where
            (p , q ) = convergent (n - 1)
            (p', q') = convergent (n - 2)
