arithmoi-0.6.0.1: Efficient basic number-theoretic functions.

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

Math.NumberTheory.MoebiusInversion

Description

Generalised Moebius inversion

Synopsis

# Documentation

generalInversion :: (Int -> Integer) -> Int -> Integer 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.

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 n is, for n > 0, the sum of [totient k | k <- [1 .. n]], computed via generalised Moebius inversion. See http://mathworld.wolfram.com/TotientSummatoryFunction.html for the formula used for totientSum.