Copyright | (c) 2012 Daniel Fischer |
---|---|

License | MIT |

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

Safe Haskell | None |

Language | Haskell2010 |

Generalised Möbius inversion

# Documentation

generalInversion :: (Num t, Vector v t) => Proxy v -> (Word -> t) -> Word -> t Source #

`generalInversion g n`

evaluates the generalised Möbius inversion of `g`

at the argument `n`

.

The generalised Möbius 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 Möbius 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
Möbius function are known. A slightly different formula, used here,
does not need the values of the Möbius 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 :: (Integral t, Vector v t) => Proxy v -> Word -> t Source #

`totientSum n`

is, for `n > 0`

, the sum of `[totient k | k <- [1 .. n]]`

,
computed via generalised Möbius inversion.
See http://mathworld.wolfram.com/TotientSummatoryFunction.html for the
formula used for `totientSum`

.

`>>>`

`import Data.Proxy`

`>>>`

3044`totientSum (Proxy :: Proxy Data.Vector.Unboxed.Vector) 100 :: Int`

`>>>`

3044`totientSum (Proxy :: Proxy Data.Vector.Vector) 100 :: Integer`