-- | Pell's Equation: /x^2 - Dy^2 = 1/.

module Euler.Util.PellEquation
    ( fundamentalSolution
    , checkSolution
    ) where

import Euler.Prelude

import Euler.Util.ContinuedFractions (sqrtConvergents)

import qualified Data.List as List

---------------------------------------------------------

checkSolution :: (Integral a)
    => a      -- ^ /D/
    -> (a, a) -- ^ /(x, y)/
    -> Bool

fundamentalSolution :: (Integral a)
    => a      -- ^ /D/
    -> Maybe (a, a)
-- ^ The fundamental solution to Pell's Equation is the
-- solution /(x, y)/ minimizing /x/.

---------------------------------------------------------

checkSolution d (x, y) = (x^2) - (d * y^2) == 1

-- https://en.wikipedia.org/w/index.php?title=Pell%27s_equation&oldid=739131845#Fundamental_solution_via_continued_fractions

fundamentalSolution d = do
    c <- sqrtConvergents d
    s <- List.find (checkSolution d) $ (numerator &&& denominator) <$> c
    pure s