module Factory.Math.PrimeFactorisation(
Algorithmic(..),
maxBoundPrimeFactor,
smoothness,
powerSmoothness,
regularNumbers,
primePowerTotient,
eulersTotient,
omega,
squareFree
) where
import qualified Control.DeepSeq
import qualified Factory.Data.Exponential as Data.Exponential
import qualified Factory.Data.PrimeFactors as Data.PrimeFactors
class Algorithmic algorithm where
primeFactors :: (Control.DeepSeq.NFData base, Integral base)
=> algorithm
-> base
-> Data.PrimeFactors.Factors base Int
maxBoundPrimeFactor :: Integral i => i -> i
maxBoundPrimeFactor :: i -> i
maxBoundPrimeFactor = Double -> i
forall a b. (RealFrac a, Integral b) => a -> b
floor (Double -> i) -> (i -> Double) -> i -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Double -> Double
forall a. Floating a => a -> a
sqrt :: Double -> Double) (Double -> Double) -> (i -> Double) -> i -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral
smoothness :: (Algorithmic algorithm, Control.DeepSeq.NFData base, Integral base) => algorithm -> [base]
smoothness :: algorithm -> [base]
smoothness algorithm
algorithm = base
0 base -> [base] -> [base]
forall a. a -> [a] -> [a]
: (base -> base) -> [base] -> [base]
forall a b. (a -> b) -> [a] -> [b]
map (Exponential base Int -> base
forall base exponent. Exponential base exponent -> base
Data.Exponential.getBase (Exponential base Int -> base)
-> (base -> Exponential base Int) -> base -> base
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Exponential base Int] -> Exponential base Int
forall a. [a] -> a
last ([Exponential base Int] -> Exponential base Int)
-> (base -> [Exponential base Int]) -> base -> Exponential base Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. algorithm -> base -> [Exponential base Int]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
primeFactors algorithm
algorithm) [base
1 ..]
powerSmoothness :: (Algorithmic algorithm, Control.DeepSeq.NFData base, Integral base) => algorithm -> [base]
powerSmoothness :: algorithm -> [base]
powerSmoothness algorithm
algorithm = base
0 base -> [base] -> [base]
forall a. a -> [a] -> [a]
: (base -> base) -> [base] -> [base]
forall a b. (a -> b) -> [a] -> [b]
map ([base] -> base
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([base] -> base) -> (base -> [base]) -> base -> base
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Exponential base Int -> base) -> [Exponential base Int] -> [base]
forall a b. (a -> b) -> [a] -> [b]
map Exponential base Int -> base
forall base exponent.
(Num base, Integral exponent) =>
Exponential base exponent -> base
Data.Exponential.evaluate ([Exponential base Int] -> [base])
-> (base -> [Exponential base Int]) -> base -> [base]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. algorithm -> base -> [Exponential base Int]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
primeFactors algorithm
algorithm) [base
1 ..]
regularNumbers :: (Algorithmic algorithm, Integral base) => algorithm -> [base]
regularNumbers :: algorithm -> [base]
regularNumbers algorithm
algorithm = ((base, Integer) -> base) -> [(base, Integer)] -> [base]
forall a b. (a -> b) -> [a] -> [b]
map (base, Integer) -> base
forall base exponent. Exponential base exponent -> base
fst ([(base, Integer)] -> [base])
-> ([Integer] -> [(base, Integer)]) -> [Integer] -> [base]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((base, Integer) -> Bool) -> [(base, Integer)] -> [(base, Integer)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= (Integer
5 :: Integer)) (Integer -> Bool)
-> ((base, Integer) -> Integer) -> (base, Integer) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (base, Integer) -> Integer
forall a b. (a, b) -> b
snd) ([(base, Integer)] -> [(base, Integer)])
-> ([Integer] -> [(base, Integer)])
-> [Integer]
-> [(base, Integer)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [base] -> [Integer] -> [(base, Integer)]
forall a b. [a] -> [b] -> [(a, b)]
zip [base
1 ..] ([Integer] -> [(base, Integer)])
-> ([Integer] -> [Integer]) -> [Integer] -> [(base, Integer)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Integer] -> [Integer]
forall a. [a] -> [a]
tail ([Integer] -> [base]) -> [Integer] -> [base]
forall a b. (a -> b) -> a -> b
$ algorithm -> [Integer]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> [base]
smoothness algorithm
algorithm
primePowerTotient :: (Integral base, Integral exponent) => Data.Exponential.Exponential base exponent -> base
primePowerTotient :: Exponential base exponent -> base
primePowerTotient (base
base, exponent
exponent') = base -> base
forall a. Enum a => a -> a
pred base
base base -> base -> base
forall a. Num a => a -> a -> a
* base
base base -> exponent -> base
forall a b. (Num a, Integral b) => a -> b -> a
^ exponent -> exponent
forall a. Enum a => a -> a
pred exponent
exponent'
eulersTotient :: (
Algorithmic algorithm,
Control.DeepSeq.NFData i,
Integral i,
Show i
) => algorithm -> i -> i
eulersTotient :: algorithm -> i -> i
eulersTotient algorithm
_ i
1 = i
1
eulersTotient algorithm
algorithm i
i
| i
i i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i
0 = [Char] -> i
forall a. HasCallStack => [Char] -> a
error ([Char] -> i) -> [Char] -> i
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Math.PrimeFactorisation.eulersTotient:\tundefined for; " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ i -> [Char]
forall a. Show a => a -> [Char]
show i
i
| Bool
otherwise = [i] -> i
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([i] -> i)
-> ([Exponential i Int] -> [i]) -> [Exponential i Int] -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Exponential i Int -> i) -> [Exponential i Int] -> [i]
forall a b. (a -> b) -> [a] -> [b]
map Exponential i Int -> i
forall base exponent.
(Integral base, Integral exponent) =>
Exponential base exponent -> base
primePowerTotient ([Exponential i Int] -> i) -> [Exponential i Int] -> i
forall a b. (a -> b) -> a -> b
$ algorithm -> i -> [Exponential i Int]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
primeFactors algorithm
algorithm i
i
omega :: (Algorithmic algorithm, Integral i) => algorithm -> [i]
omega :: algorithm -> [i]
omega algorithm
algorithm = (Integer -> i) -> [Integer] -> [i]
forall a b. (a -> b) -> [a] -> [b]
map (Int -> i
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> i) -> (Integer -> Int) -> Integer -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Exponential Integer Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Exponential Integer Int] -> Int)
-> (Integer -> [Exponential Integer Int]) -> Integer -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. algorithm -> Integer -> [Exponential Integer Int]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
primeFactors algorithm
algorithm) [Integer
0 :: Integer ..]
squareFree :: (Algorithmic algorithm, Control.DeepSeq.NFData i, Integral i) => algorithm -> [i]
squareFree :: algorithm -> [i]
squareFree algorithm
algorithm = (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
filter (
(Exponential i Int -> Bool) -> [Exponential i Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (
(Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1) (Int -> Bool)
-> (Exponential i Int -> Int) -> Exponential i Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential i Int -> Int
forall a b. (a, b) -> b
Data.Exponential.getExponent
) ([Exponential i Int] -> Bool)
-> (i -> [Exponential i Int]) -> i -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. algorithm -> i -> [Exponential i Int]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
primeFactors algorithm
algorithm
) [i
1 ..]