module Solutions.P34 (totient,totientFiltered) where
import Data.List (genericLength)
import Problems.P33
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
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]