Portability | Non-portable (GHC extensions) |
---|---|

Stability | Provisional |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Safe Haskell | None |

Generalised Moebius inversion

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

# 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 :: Int -> IntegerSource

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