{-
Copyright (C) 2011 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 .
-}
{- |
[@AUTHOR@] Dr. Alistair Ward
[@DESCRIPTION@]
* .
* 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/; .
* 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 Data.List
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/.
* NB: 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 = floor . (sqrt :: Double -> Double) . fromIntegral
{- |
* A constant, zero-indexed, conceptually infinite, list, of the /smooth/ness of all positive integers.
* .
* .
-}
smoothness :: (Algorithmic algorithm, Control.DeepSeq.NFData base, Integral base) => algorithm -> [base]
smoothness algorithm = 0 : map (Data.Exponential.getBase . last . primeFactors algorithm) [1 ..]
{- |
* A constant, zero-indexed, conceptually infinite, list of the /power-smooth/ness of all positive integers.
* .
-}
powerSmoothness :: (Algorithmic algorithm, Control.DeepSeq.NFData base, Integral base) => algorithm -> [base]
powerSmoothness algorithm = 0 : map (maximum . map Data.Exponential.evaluate . primeFactors algorithm) [1 ..]
{- |
* Filters 'smoothness', to derive the constant list of /Hamming-numbers/.
* .
-}
regularNumbers :: (Algorithmic algorithm, Control.DeepSeq.NFData base, Integral base) => algorithm -> [base]
regularNumbers algorithm = map fst . filter ((<= (5 :: Integer)) . snd) . zip [1 ..] . tail $ smoothness 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 (base, exponent') = pred base * base ^ pred exponent'
{- |
* The number of /coprimes/ less than or equal to the specified positive integer.
* .
* .
* AKA /EulerPhi/.
-}
eulersTotient :: (
Algorithmic algorithm,
Control.DeepSeq.NFData i,
Integral i,
Show i
) => algorithm -> i -> i
eulersTotient _ 1 = 1
eulersTotient algorithm i
| i <= 0 = error $ "Factory.Math.PrimeFactorisation.eulersTotient:\tundefined for; " ++ show i
| otherwise = product . map primePowerTotient $ primeFactors algorithm i
{- |
* A constant, zero-indexed, conceptually infinite, list of the /small omega/ numbers (i.e. the number of /distinct/ prime factors); cf. /big omega/.
* .
*
* .
-}
omega :: (Algorithmic algorithm, Control.DeepSeq.NFData i, Integral i) => algorithm -> [i]
omega algorithm = map (Data.List.genericLength . primeFactors algorithm) [0 :: Integer ..]
{- |
* A constant, conceptually infinite, list of the /square-free/ numbers, i.e. those which aren't divisible by any /perfect square/.
* .
-}
squareFree :: (Algorithmic algorithm, Control.DeepSeq.NFData i, Integral i) => algorithm -> [i]
squareFree algorithm = filter (all (== 1) . map Data.Exponential.getExponent . primeFactors algorithm) [1 ..]