fact package:arithmoi

Restore a number from its factorisation.

Factorise a number into a product of prime powers. Factorisation of 0 is an undefined behaviour. Otherwise following invariants hold:

abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n)))
all ((> 0) . snd) (factorise n)

>>> factorise (1 :: Integer)
[]

>>> factorise (-1 :: Integer)
[]

>>> factorise (6 :: Integer)
[(Prime 2,1),(Prime 3,1)]

>>> factorise (-108 :: Integer)
[(Prime 2,2),(Prime 3,3)]

This function is a replacement for factorise. If you were looking for the latter, please import Math.NumberTheory.Primes.Factorisation instead of this module. Warning: there are no guarantees of any particular order of prime factors, do not expect them to be ascending. E. g.,

>>> factorise 10251562501
[(Prime 101701,1),(Prime 100801,1)]

Infinite zero-based table of factorials.

>>> take 5 factorial
[1,1,2,6,24]

The time-and-space behaviour of factorial is similar to described in Math.NumberTheory.Recurrences.Bilinear#memory.

Prime factors of a factorial.

factorialFactors n == factorise (factorial !! n)

>>> factorialFactors 10
[(Prime 2,8),(Prime 3,4),(Prime 5,2),(Prime 7,1)]

Convert to a function on prime factorisation.

This singleton data type establishes a correspondence between a modulo m on type level and its factorisation on term level.

Create a singleton from factors. Factors must be distinct, as in output of factorise.

Invert sfactorsToCyclicGroup.

>>> import Data.Maybe

>>> cyclicGroupToSFactors (fromJust (sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)))
SFactors {unSFactors = [(Prime 2,2)]}

Convert a singleton to a proof that m is known. Usage example:

toModulo :: SFactors Integer m -> Natural
toModulo t = case proofFromSFactors t of Sub Dict -> natVal t

Create a singleton from a type-level positive modulo m, passed in a constraint.

>>> :set -XDataKinds

>>> sfactors :: SFactors Integer 13
SFactors {unSFactors = [(Prime 13,1)]}

Check whether a multiplicative group of residues, characterized by its modulo, is cyclic and, if yes, return its form.

>>> :set -XTypeOperators -XNoStarIsType

>>> import GHC.TypeNats

>>> sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)
Just CG4'

>>> sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))
Just (CGDoubleOddPrimePower' (Prime 13) 3)

>>> sfactorsToCyclicGroup (sfactors :: SFactors Integer  (4 * 13))
Nothing

Create a singleton from factors of m. Factors must be distinct, as in output of factorise.

>>> import Math.NumberTheory.Primes

>>> someSFactors (factorise 98)
SFactors {unSFactors = [(Prime 2,1),(Prime 7,2)]}

Factors of m.

List all square roots modulo a number, the factorisation of which is passed as a second argument.

>>> sqrtsModFactorisation 1 (factorise 60)
[1,49,41,29,31,19,11,59]

Type for numbers, accompanied by their factorisation.

A container for a number and its pairwise coprime (but not necessarily prime) factorisation. It is designed to preserve information about factors under multiplication. One can use this representation to speed up prime factorisation and computation of arithmetic functions. For instance, let p and q be big primes:

>>> let p = 1000000000000000000000000000057 :: Integer

>>> let q = 2000000000000000000000000000071 :: Integer

It would be difficult to compute the totient function of their product as is, because once we multiplied them the information of factors is lost and totient (p * q) would take ages. Things become different if we simply change types of p and q to prefactored ones:

>>> let p = 1000000000000000000000000000057 :: Prefactored Integer

>>> let q = 2000000000000000000000000000071 :: Prefactored Integer

Now the totient function can be computed instantly:

>>> import Math.NumberTheory.ArithmeticFunctions

>>> prefValue $ totient (p^2 * q^3)
8000000000000000000000000001752000000000000000000000000151322000000000000000000000006445392000000000000000000000135513014000000000000000000001126361040

>>> prefValue $ totient $ totient (p^2 * q^3)
2133305798262843681544648472180210822742702690942899511234131900112583590230336435053688694839034890779375223070157301188739881477320529552945446912000

Let us look under the hood:

>>> import Math.NumberTheory.ArithmeticFunctions

>>> prefFactors $ totient (p^2 * q^3)
Coprimes {unCoprimes = [(1000000000000000000000000000057,1),(41666666666666666666666666669,1),(2000000000000000000000000000071,2),(111111111111111111111111111115,1),(2,4),(3,3)]}

>>> prefFactors $ totient $ totient (p^2 * q^3)
Coprimes {unCoprimes = [(39521,1),(227098769,1),(22222222222222222222222222223,1),(2000000000000000000000000000071,1),(361696272343,1),(85331809838489,1),(6046667,1),(199937,1),(5,3),(41666666666666666666666666669,1),(2,22),(3,8)]}

Pairwise coprimality of factors is crucial, because it allows us to process them independently, possibly even in parallel or concurrent fashion. Following invariant is guaranteed to hold:

abs (prefValue x) = abs (product (map (uncurry (^)) (prefFactors x)))

Create Prefactored from a given list of pairwise coprime (but not necessarily prime) factors with multiplicities.

>>> fromFactors (splitIntoCoprimes [(140, 1), (165, 1)])
Prefactored {prefValue = 23100, prefFactors = Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}}

>>> fromFactors (splitIntoCoprimes [(140, 2), (165, 3)])
Prefactored {prefValue = 88045650000, prefFactors = Coprimes {unCoprimes = [(28,2),(33,3),(5,5)]}}

A class for unique factorisation domains.

Prime factors of a binomial coefficient.

binomialFactors n k == factorise (binomial !! n !! k)

>>> binomialFactors 10 4
[(Prime 2,1),(Prime 3,1),(Prime 5,1),(Prime 7,1)]