If you've ever taken some lessons on competitive programming, chances are that you have already heard about one of the most famous formula: the Möbius inversion. This article is aimed to provide some basic insight on what is the Möbius inversion, as well as how to apply it in various programming tasks.

Prequisite

If you are not familiar with the linear sieve and multiplicative functions, it is recommended that you read about them first here.

I will introduce some frequently used notations and lemmas first.

Notation

1. [P] refers to the boolean expression, i.e. [P] = 1 when P is true, and 0 otherwise.
2. ⌊ x⌋ refers to rounding x down to the nearest integer. Thus refers to the integer division.
3. d|n means that d can divide n (without a remainder).

The following functions are all multiplicative functions, where p is a prime number and k is a positive integer.

1. The constant function I(p^k) = 1.
2. The identity function Id(p^k) = p^k.
3. The power function Id_a(p^k) = p^ak, where a is constant.
4. The unit function .
5. The divisor function , denoting the sum of the a-th powers of all the positive divisors of the number.
6. The Möbius function μ(p^k) = [k = 0] - [k = 1].
7. The Euler's totient function φ(p^k) = p^k - p^k - 1.

Lemma

I have some my unofficial names for these frequently used conclusions. If you happen to know any more commonly used name for them, you are more than welcome to tell me.

• ( The integer division lemma ) For every positive integer p, q and r, .

Proof: We know that . Hence . Since the fraction part of cannot exceed , we achieve the conclusion.

• ( The harmonic lemma ) Consider the harmonic sequence on integer division .

1. The sequence is non-increasing, and there are at most different elements.
2. The sum of the sequence is approximate to .

Proof: Denote . For every i not exceeding , there will be no more than values in the domain of d(i), so there can be at most different values for d(i). For the rest part of i greater than , we can infer that and is a positive integer, so there can be at most different values for d(i). Therefore we know that there are at most different elements in the sequence.

Since the Euler–Mascheroni constant states that , we know that , so the sum of the original sequence is approximate to .

Moreover, it is actually possible to exploit the property that the sequence has at most different elements, and write a loop that runs in complexity to iterate through every possible value of d(i), using the fact that the greatest integer x satisfying d(x) = d(i) is . The piece of code below demonstrates one way to program it.

for (int i = 1, la; i <= n; i = la + 1) {
	la = n / (n / i);
	//n / x yields the same value for i <= x <= la.
}

• ( The transitive property of multiplicative functions )

1. If both f(x) and g(x) are multiplicative, then h(x) = f(x)g(x) is also multiplicative.
2. If both f(x) and g(x) are multiplicative, then their Dirichlet convolution is also multiplicative. Specifically, if f(x) is multiplicative, is also multiplicative.

The proof is more mathematical, which I will skip here.

What is the Möbius inversion?

According to Wikipedia, the Möbius inversion states that:

If for every positive integer n, then , where μ(x) is the Möbius function, which is multiplicative and satisfies f(1) = 1, f(p) =  - 1, f(p^k) = 0 for any prime number p and any integer k ≥ 2. ( It is worth noting that you can pre-compute all values of the Möbius function from 1 to n using the linear sieve. )

However, the definition alone does not mean much (unless the problem statement explicitly gives you something like . In that case, well...). There is one important property that is probably more useful than the definition:

In order to prove this property, we have to use the transitive property of multiplicative functions to show that is multiplicative. After that, we can see f(1) = 1 and f(p^k) = 0, which means f(x) = ε(x). Now you may ask: why is this property important? I think it is best to show the reasons in some basic examples below.

Example 1. Find out the number of co-prime pairs of integers (x, y) in range [1, n].

Solution 1. Notice that the question is the same as asking you the value of

Now apply the Möbius inversion on [gcd(i, j)] = 1, we have

which is the same as

Notice that [d|gcd(i, j)] = [d|i][d|j]. Therefore

We can change the order of summing things up, so

We know that . Thus

Then we can simply loop through 1 to n to compute the formula. While we can optimize this loop to using the harmonic lemma, we still have to use the linear sieve to pre-compute the values of μ(d). Therefore, the overall complexity of the algorithm is O(n).

Example 2. Find out the sum of gcd(x, y) for every pair of integers (x, y) in range [1, n] (gcd(x, y) means the greatest common divisor of x and y).

Solution 2. Similar as above, notice that the question is the same as asking you the value of

Let k = gcd(i, j). We can then loop for k first.

Now assume i = ak, j = bk, and then

It can be observed that the last part of the formula is the same as the one in example 1. Applying the same procedure, we have

According to the harmonic lemma, . Therefore, if we compute the sum above with brute force, the overall complexity will be .

This is, however, not the best complexity we can achieve with the Möbius inversion. Now let l = kd, and we can loop for l first.

Applying the transitive property of multiplicative functions, we can see that is multiplicative. Moreover, we have g(p^k) = p^k - p^k - 1. If you have somewhat studied about the number theory, you may figure out that g(l) is actually the Euler's totient function. Regardless of whether you know about the coincidence or not, g(l) can be pre-computed with the linear sieve, and , which can be simply computed in O(n) complexity.

Example 3. Find out the sum of lcm(x, y) for every pair of integers (x, y) in range [1, n] (lcm(x, y) means the least common multiple of x and y).

Solution 3. Well, we should be pretty familiar with the techniques by now. First of all, the answer should be

Since , let k = gcd(i, j). We can then loop for k first.

Now assume i = ak, j = bk, and then

Now let's proceed to assume a = dp, b = dq, then

Now notice , and we have

Now following the example above, let l = kd, and then

Notice that is also multiplicative, and g(p^k) = p^k - p^k + 1. We can pre-compute the values of g(l) via the linear sieve, and . The overall complexity will be O(n).

Example 4. Find out the sum of lcm(A[i], A[j]) for every pair of integers (A[i], A[j]) with an array A of length N (1 ≤ i, j ≤ N), with the constraint of 1 ≤ N ≤ 200, 000 and 1 ≤ A[i] ≤ 1, 000, 000.

Solution 4. This is a common variation of the example above. Denote

We simply have

Let t = dl, then

Now, similar to the example above is multiplicative with g(p^k) = p^- k - p^{- k + 1}, and thus can be computed with O(V), where V is the range span of A. The latter part of the formula is also fairly easy to figure out if you keep track of the number of the elements equal to v as cnt(v), since

and with the harmonic lemma, the above computation can be done in . Hence the overall complexity is .

Practice Problems

Simple Sum

(Thanks Bashca for showing me this one!)

Link

GCD

Link

Sky Code

Link

Extensions

It is known that all examples above can be further optimized to . The exact technique will (probably) be introduced in the upcoming article.

Update: The article introducing the optimization is ready here.

Finally, thanks Tommyr7 for his effort in the article!