Safe Haskell | None |
---|---|

Language | Haskell2010 |

`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.

- class Algorithmic algorithm where
- maxBoundPrimeFactor :: Integral i => i -> i
- smoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base]
- powerSmoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base]
- regularNumbers :: (Algorithmic algorithm, Integral base) => algorithm -> [base]
- primePowerTotient :: (Integral base, Integral exponent) => Exponential base exponent -> base
- eulersTotient :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> i
- omega :: (Algorithmic algorithm, Integral i) => algorithm -> [i]
- squareFree :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i]

# Type-classes

class Algorithmic algorithm where Source #

Defines the methods expected of a *factorisation*-algorithm.

# Functions

maxBoundPrimeFactor :: Integral i => i -> i Source #

- 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`

for an even number, but though a prime-factor`div`

2)*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.

smoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] Source #

- A constant, zero-indexed, conceptually infinite, list, of the
*smooth*ness of all positive integers. - https://en.wikipedia.org/wiki/Smooth_number.
- http://mathworld.wolfram.com/SmoothNumber.html.

powerSmoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] Source #

- 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.

regularNumbers :: (Algorithmic algorithm, Integral base) => algorithm -> [base] Source #

- Filters
`smoothness`

, to derive the constant list of*Hamming-numbers*. - https://en.wikipedia.org/wiki/Regular_number.

primePowerTotient :: (Integral base, Integral exponent) => Exponential base exponent -> base Source #

*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.

eulersTotient :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> i Source #

- The number of
*coprimes*less than or equal to the specified positive integer. - https://en.wikipedia.org/wiki/Euler%27s_totient_function.
- http://mathworld.wolfram.com/TotientFunction.html.
- AKA
*EulerPhi*.

omega :: (Algorithmic algorithm, Integral i) => algorithm -> [i] Source #

- 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.

squareFree :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i] Source #

- 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.