Copyright | (c) 2012 Daniel Fischer |
---|---|
License | MIT |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Generalised Möbius inversion
Synopsis
- generalInversion :: (Int -> Integer) -> Int -> Integer
- totientSum :: Int -> Integer
Documentation
generalInversion :: (Int -> Integer) -> Int -> Integer 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 :: Int -> Integer 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
.