module Math.NumberTheory.Primes.Factorisation.Utils
( ppTotient
, totientFromCanonical
, carmichaelFromCanonical
, divisorsFromCanonical
, tauFromCanonical
, divisorSumFromCanonical
, sigmaFromCanonical
) where
import Data.Set (Set)
import qualified Data.Set as Set
import Data.Bits
import Data.List
import Math.NumberTheory.Powers.Integer
ppTotient :: (Integer,Int) -> Integer
ppTotient (p,1) = p1
ppTotient (p,k) = (p1)*(integerPower p (k1))
totientFromCanonical :: [(Integer,Int)] -> Integer
totientFromCanonical = product . map ppTotient
carmichaelFromCanonical :: [(Integer,Int)] -> Integer
carmichaelFromCanonical = go2
where
go2 ((2,k):ps) = let acc = case k of
1 -> 1
2 -> 2
_ -> 1 `shiftL` (k2)
in go acc ps
go2 ps = go 1 ps
go !acc ((p,1):pps) = go (lcm acc (p1)) pps
go acc ((p,k):pps) = go ((lcm acc (p1))*integerPower p (k1)) pps
go acc [] = acc
divisorsFromCanonical :: [(Integer,Int)] -> Set Integer
divisorsFromCanonical = foldl' step (Set.singleton 1)
where
step st (p,k) = Set.unions (st:[Set.mapMonotonic (*pp) st | pp <- take k (iterate (*p) p) ])
tauFromCanonical :: [(a,Int)] -> Integer
tauFromCanonical pps = product [fromIntegral k + 1 | (_,k) <- pps]
divisorSumFromCanonical :: [(Integer,Int)] -> Integer
divisorSumFromCanonical = product . map ppDivSum
ppDivSum :: (Integer,Int) -> Integer
ppDivSum (p,1) = p+1
ppDivSum (p,k) = (p^(k+1)1) `quot` (p1)
sigmaFromCanonical :: Int -> [(Integer,Int)] -> Integer
sigmaFromCanonical k = product . map (ppDivPowerSum k)
ppDivPowerSum :: Int -> (Integer,Int) -> Integer
ppDivPowerSum k (p,m) = (p^(k*(m+1)) 1) `quot` (p^k 1)