fact -package:reflex

A Fact p is an implicit proof of p, propagated by Haskell's constraint solver. Facts can be used to implicitly introduce or propagate proofs. However, there is a small run-time cost associated with using Facts: typeclass dictionaries for Facts are still passed around. In many cases they will be optimized away, but this is not guaranteed.

Compute the factorial function n!. Returns +∞ if the input is above 170 (above which the result cannot be represented by a 64-bit Double).

Returns a list of all prime factors; inverse of mconcat.

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)]

Exact factorial numbers. For a fast approximation see math-functions:Numeric.SpecFunctions.factorial instead. The naive definition of the factorial numbers is:

factorial n
| n < 0     = 0
| otherwise = product [1..n]

However, we use a fast algorithm based on the split-recursive form:

factorial n =
2^(n - popCount n) * product [(q k)^k | forall k, k >= 1]
where
q k = product [j | forall j, n*2^(-k) < j <= n*2^(-k+1), odd j]

Create a default factorization diagram for the given integer, by factoring it and calling factorDiagram' on its prime factorization (with the factors ordered from smallest to biggest).

import Diagrams.TwoD.Factorization
factorDiagramEx = factorDiagram 700

Create a centered factorization diagram from the given list of factors (intended to be primes, but again, any positive integers will do; note how the below example uses 6), by recursively folding according to primeLayout, with the defaultColors and a base case of a black circle.

import Diagrams.TwoD.Factorization
factorDiagram'Ex = factorDiagram' [2,5,6]

Not on Stackage, so not searched. Rational arithmetic in an irrational world.