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

Copyright (c) 2012 Daniel Fischer MIT Daniel Fischer Provisional Non-portable (GHC extensions) None Haskell98

Math.NumberTheory.MoebiusInversion.Int

Description

Generalised Moebius inversion for `Int` valued functions.

Synopsis

# Documentation

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

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