arithmoi-0.4.0.1: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.

Portability Non-portable (GHC extensions) Provisional Daniel Fischer Safe-Infered

Math.NumberTheory.MoebiusInversion

Description

Generalised Moebius inversion

Synopsis

Documentation

generalInversion :: (Int -> Integer) -> Int -> IntegerSource

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

Since the function arguments are used as array indices, the domain of `f` is restricted to `Int`.

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