{- 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 <http://www.gnu.org/licenses/>. -} {- | [@AUTHOR@] Dr. Alistair Ward [@DESCRIPTION@] * <http://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/; <http://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 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. * <http://en.wikipedia.org/wiki/Smooth_number>. * <http://mathworld.wolfram.com/SmoothNumber.html>. -} 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. * <http://en.wikipedia.org/wiki/Smooth_number#Powersmooth_numbers>. -} 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/. * <http://en.wikipedia.org/wiki/Regular_number>. -} 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. * <http://en.wikipedia.org/wiki/Euler%27s_totient_function>. * <http://mathworld.wolfram.com/TotientFunction.html>. * 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/. * <http://oeis.org/wiki/Omega%28n%29,_number_of_distinct_primes_dividing_n>. * <http://mathworld.wolfram.com/DistinctPrimeFactors.html> * <http://planetmath.org/encyclopedia/NumberOfDistinctPrimeFactorsFunction.html>. -} 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/. * <http://en.wikipedia.org/wiki/Square-free_integer>. -} squareFree :: (Algorithmic algorithm, Control.DeepSeq.NFData i, Integral i) => algorithm -> [i] squareFree algorithm = filter (all (== 1) . map Data.Exponential.getExponent . primeFactors algorithm) [1 ..]