Math.NumberTheory.MoebiusInversion.Int

Generalised Moebius inversion for Int valued functions.

Documentation

generalInversion :: (Int -> Int) -> Int -> Int

generalInversion g n evaluates the generalised Moebius inversion of g at the argument n.

The generalised Moebius inversion implemented here allows an efficient calculation of isolated values of the function f : N -> Z if the function g defined by

 g n = sum [f (n `quot` k) | k <- [1 .. n]]

can be cheaply computed. By the generalised Moebius inversion formula, then

 f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]

which allows the computation in O(n) steps, if the values of the Moebius function are known. A slightly different formula, used here, does not need the values of the Moebius function and allows the computation in O(n^0.75) steps, using O(n^0.5) memory.

An example of a pair of such functions where the inversion allows a more efficient computation than the direct approach is

 f n = number of reduced proper fractions with denominator <= n
 g n = number of proper fractions with denominator <= n

(a proper fraction is a fraction 0 < n/d < 1). Then f n is the cardinality of the Farey sequence of order n (minus 1 or 2 if 0 and/or 1 are included in the Farey sequence), or the sum of the totients of the numbers 2 <= k <= n. f n is not easily directly computable, but then g n = n*(n-1)/2 is very easy to compute, and hence the inversion gives an efficient method of computing f n.

For Int valued functions, unboxed arrays can be used for greater efficiency. That bears the risk of overflow, however, so be sure to use it only when it's safe.

The value f n is then computed by generalInversion g n). Note that when many values of f are needed, there are far more efficient methods, this method is only appropriate to compute isolated values of f.

totientSum :: Int -> Int

totientSum n is, for n > 0, the sum of [totient k | k <- [1 .. n]], computed via generalised Moebius inversion. Arguments less than 1 cause an error to be raised.