arithmoi-0.13.2.0: Efficient basic number-theoretic functions.

Copyright | (c) 2012 Daniel Fischer
License | MIT
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com>
Safe Haskell | None
Language | Haskell2010

Math.NumberTheory.MoebiusInversion

Description

Generalised Möbius inversion

Synopsis

- generalInversion :: forall t (v :: Type -> Type). (Num t, Vector v t) => Proxy v -> (Word -> t) -> Word -> t
- totientSum :: forall t (v :: Type -> Type). (Integral t, Vector v t) => Proxy v -> Word -> t

# Documentation

generalInversion :: forall t (v :: Type -> Type). (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 :: forall t (v :: Type -> Type). (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
    >>> totientSum (Proxy :: Proxy Data.Vector.Unboxed.Vector) 100 :: Int
    3044
    >>> totientSum (Proxy :: Proxy Data.Vector.Vector) 100 :: Integer
    3044