{- |
Description: Euler's totient function
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P34" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P34 (totient,totientFiltered) where

import           Data.List    (genericLength)
import           Problems.P33

-- | Calculate Euler's totient function \(\phi(m)\).
--
-- Accumulates count of numbers that are coprime.
totient :: Integral a => a -> a
totient :: forall a. Integral a => a -> a
totient a
m = a -> a -> a
forall {t}. Num t => a -> t -> t
accumulate a
m a
0
  where accumulate :: a -> t -> t
accumulate a
0 t
phi = t
phi
        accumulate a
r t
phi
          | a -> a -> Bool
forall a. Integral a => a -> a -> Bool
coprime a
m a
r = a -> t -> t
accumulate (a
ra -> a -> a
forall a. Num a => a -> a -> a
-a
1) (t
phit -> t -> t
forall a. Num a => a -> a -> a
+t
1)
          | Bool
otherwise   = a -> t -> t
accumulate (a
ra -> a -> a
forall a. Num a => a -> a -> a
-a
1) t
phi

-- | Calculate Euler's totient function \(\phi(m)\).
--
-- Filters through numbers that are coprime and count them.
totientFiltered :: Integral a => a -> a
totientFiltered :: forall a. Integral a => a -> a
totientFiltered a
m = [a] -> a
forall i a. Num i => [a] -> i
genericLength ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a -> a -> Bool
forall a. Integral a => a -> a -> Bool
coprime a
m) [a
1..a
m]