{-
	Copyright (C) 2011-2015 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]

	* <https://en.wikipedia.org/wiki/Integer_factorization>.

	* Exports a common interface to permit decomposition of positive integers,
	into the unique combination of /prime/-factors known to exist according to the /Fundamental Theorem of Arithmetic/; <https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic>.

	* Leveraging this abstract capability, it derives the /smoothness/, /power-smoothness/, /omega/-numbers and /square-free/ integers.

	* Filters the list of /regular-numbers/ from the list of /smoothness/.

	* CAVEAT: to avoid wasting time, it may be advantageous to check /Factory.Math.Primality.isPrime/ first.
-}

module Factory.Math.PrimeFactorisation(
-- * Type-classes
	Algorithmic(..),
-- * Functions
	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

-- | Defines the methods expected of a /factorisation/-algorithm.
class Algorithmic algorithm	where
	primeFactors	:: (Control.DeepSeq.NFData base, Integral base)
		=> algorithm
		-> base	-- ^ The operand
		-> Data.PrimeFactors.Factors base Int {-arbitrarily-}

{- |
	* The upper limit for a prime to be considered as a candidate factor of the specified number.

	* One might naively think that this limit is @(x `div` 2)@ for an even number,
	but though a prime-factor /greater/ than the /square-root/ of the number can exist,
	its smaller /cofactor/ decomposes to a prime which must be less than the /square-root/.

	* N.B.: rather then using @(primeFactor <= sqrt numerator)@ to filter the candidate prime-factors of a given numerator,
	one can alternatively use @(numerator >= primeFactor ^ 2)@ to filter what can potentially be factored by a given prime-factor.

	* CAVEAT: suffers from rounding-errors, though no consequence has been witnessed.
-}
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

{- |
	* A constant, zero-indexed, conceptually infinite, list, of the /smooth/ness of all positive integers.

	* <https://en.wikipedia.org/wiki/Smooth_number>.

	* <https://mathworld.wolfram.com/SmoothNumber.html>.
-}
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 ..]

{- |
	* A constant, zero-indexed, conceptually infinite, list of the /power-smooth/ness of all positive integers.

	* <https://en.wikipedia.org/wiki/Smooth_number#Powersmooth_numbers>.
-}
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 ..]

{- |
	* Filters 'smoothness', to derive the constant list of /Hamming-numbers/.

	* <https://en.wikipedia.org/wiki/Regular_number>.
-}
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

{- |
	* /Euler's Totient/ for a /power/ of a /prime/-number.

	* By /Olofsson/; @(phi(n^k) = n^(k - 1) * phi(n))@
	and since @(phi(prime) = prime - 1)@

	* CAVEAT: checks neither the primality nor the bounds of the specified value; therefore for internal use only.
-}
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'

{- |
	* The number of /coprimes/ less than or equal to the specified positive integer.

	* <https://en.wikipedia.org/wiki/Euler%27s_totient_function>.

	* <https://mathworld.wolfram.com/TotientFunction.html>.

	* AKA /EulerPhi/.
-}
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

{- |
	* A constant, zero-indexed, conceptually infinite, list of the /small omega/ numbers (i.e. the number of /distinct/ prime factors); cf. /big omega/.

	* <https://oeis.org/wiki/Omega%28n%29,_number_of_distinct_primes_dividing_n>.

	* <https://mathworld.wolfram.com/DistinctPrimeFactors.html>

	* <https://planetmath.org/encyclopedia/NumberOfDistinctPrimeFactorsFunction.html>.
-}
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 ..]

{- |
	* A constant, conceptually infinite, list of the /square-free/ numbers, i.e. those which aren't divisible by any /perfect square/.

	* <https://en.wikipedia.org/wiki/Square-free_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 ..]