Multiplicative functions and Mobius inversion

Why this matters when you build with AI

Counting problems are where AI tools are most confidently wrong. Ask for "the number of pairs with no common factor" and the first answer is often a double loop over all pairs with a gcd check. That works for 100 numbers, but with bounds near 10^5 it checks 10^10 pairs, which is too slow on a typical judge. The fix is a formula, and the formula is not something most code generators reach for unless you name it.

This lesson gives you that formula. The Mobius function is a small table of signs that turns "count the pairs with exactly this property" into "sum a few products of floor divisions". You will also learn how to test the formula, because a sign error or a missing zero gives an answer that is close enough to look right.

When you review AI output for counting code, look for three things: a double loop that should be a sum over divisors, a missing long long, and an off-by-one in the range that is subtracted. Each one is covered below with a test that catches it.

Multiplicative functions in plain words

A function f on positive integers is multiplicative when f(1) = 1 and f(a * b) = f(a) * f(b) whenever a and b share no prime factor. Two examples:

d(n), the number of divisors. d(12) = 6 and d(4) * d(3) = 3 * 2 = 6.
phi(n), Euler's totient, which counts the numbers from 1 to n with no common factor with n. It is covered in its own lesson.

The Mobius function mu(n) is the third one. Its values depend only on the prime factors of n:

mu(1) = 1.
mu(n) = 0 if some prime divides n twice. Examples: mu(4) = 0, mu(12) = 0.
mu(n) = (-1)^k if n is a product of k different primes. Examples: mu(2) = -1, mu(6) = 1, mu(30) = -1.

Check mu(6) = 1 by hand. The number 6 is 2 times 3, two different primes, so k = 2 and (-1)^2 = 1.

The first 30 values, which we printed with the Python program later in this lesson, are:

mu(1..30): 1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 0 1 1 -1 0 0 1 0 0 -1 -1

Dirichlet convolution: the idea with a worked example

The Dirichlet convolution of two functions f and g is a new function:

(f * g)(n) = the sum of f(d) * g(n / d) over all divisors d of n.

Take f = mu and g = the function that is 1 for every n. Then (mu * 1)(n) is the sum of mu(d) over the divisors d of n. For n = 12, the divisors are 1, 2, 3, 4, 6 and 12, with Mobius values 1, -1, -1, 0, 1 and 0. The sum is 0.

The identity holds for every n: the sum of mu(d) over the divisors of n is 1 when n = 1 and 0 otherwise. We checked this for every n up to 3000 with a direct loop, and the test found 0 mismatches. The identity is the reason the Mobius function is useful: it cancels out the contribution of every divisor.

Mobius inversion

Suppose you know a function G where G(n) is a sum over the multiples of some hidden quantity, and you want the hidden quantity back. The general rule is:

If G(n) = sum of F(d) over d dividing n, then F(n) = sum of mu(d) * G(n / d) over d dividing n.

Here is a concrete case that matches the counting problem below. Let A = 10 and B = 10. For a number k, let G(k) be the number of pairs (x, y) with 1 <= x <= A and 1 <= y <= B such that k divides both x and y. Then G(k) = floor(A / k) * floor(B / k), because x must be a multiple of k and so must y.

Every pair has some gcd g, and it is counted in G(k) for every k that divides g. Inversion gives the number of pairs whose gcd is exactly 1:

k   mu(k)   floor(10/k)^2   mu(k) * floor(10/k)^2
1    1         100             100
2   -1          25             -25
3   -1           9              -9
4    0           4               0
5   -1           4              -4
6    1           1               1
7   -1           1              -1
8    0           1               0
9    0           1               0
10   1           1               1
sum                             63

The sum is 63, so there are 63 pairs in the 10 by 10 grid with gcd 1. A brute-force count gives 63 too, and we checked it in Python.

The counting formula

Generalise the table. For any A and B:

coprime(A, B) = the sum over d from 1 to min(A, B) of mu(d) * floor(A / d) * floor(B / d).

The terms with mu(d) = 0 contribute nothing, so only square-free d matter. Doing the sum one d at a time takes O(min(A, B)) steps. For many queries that is too slow, so the code groups consecutive d values that share the same floor(A / d) and the same floor(B / d). Inside a group, the floor values do not change, so the group contributes one product times a difference of prefix sums of mu. Grouping (the same idea used in the counting lesson) brings each query down to about 2 * (sqrt(A) + sqrt(B)) steps.

For a rectangle [L1, R1] x [L2, R2], use inclusion-exclusion on the prefix counts:

rect = coprime(R1, R2) - coprime(L1 - 1, R2) - coprime(R1, L2 - 1) + coprime(L1 - 1, L2 - 1).

Subtract the pairs with x < L1, subtract the pairs with y < L2, and add back the pairs with both, which were subtracted twice.

Sieving mu in linear time

To use the formula you need mu for every d up to the largest bound. The linear sieve from the sieves lesson computes the smallest prime factor of each number in linear time. The same loop computes mu:

Start with mu(1) = 1.
When i is prime, mu(i) = -1.
For each prime p in the list with p * i <= N, set mu(p * i) = -mu(i) if p does not divide i.
If p divides i, set mu(p * i) = 0, because p now divides p * i twice, and stop the inner loop.

Example with i = 6. The primes found so far are 2, 3 and 5. For p = 2, 2 divides 6, so mu(12) = 0 and the loop stops. We never reach p = 3 for i = 6, which is correct, because mu(18) is set when i = 9 and p = 2.

The stop is what keeps numbers with a square factor at 0. Without it, the loop writes a non-zero value for them, and Practice 5 shows the first one.

Worked problem: coprime pairs in rectangles

You receive q queries. Each query gives L1 R1 L2 R2 with 1 <= L1 <= R1 <= 10^7 and 1 <= L2 <= R2 <= 10^7. For each query, print the number of pairs (x, y) with L1 <= x <= R1, L2 <= y <= R2 and gcd(x, y) = 1.

Input and output with the program below:

63
19
25

Check the answers by hand if you like. For 1 5 1 5, the coprime pairs are the 19 pairs we count in the brute-force test, and 3 7 2 9 has 25 coprime pairs. The program agrees with a Python brute-force count on all three queries.

The C++ program (C++17, compiled with g++ -O2):

// Coprime pair counting with the Mobius function.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<int> mu, primes;
vector<ll> Mpref;   // Mpref[n] = mu(1) + ... + mu(n)
 
void build(int N) {
    mu.assign(N + 1, 0);
    vector<char> composite(N + 1, 0);
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!composite[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if ((ll)i * p > N) break;
            composite[i * p] = 1;
            if (i % p == 0) { mu[i * p] = 0; break; }   // p^2 divides i*p
            mu[i * p] = -mu[i];
        }
    }
    Mpref.assign(N + 1, 0);
    for (int i = 1; i <= N; i++) Mpref[i] = Mpref[i - 1] + mu[i];
}
 
// Number of pairs (x, y) with 1 <= x <= A, 1 <= y <= B and gcd(x, y) = 1.
// Uses sum over d of mu(d) * floor(A/d) * floor(B/d), grouped into blocks.
ll count_coprime(ll A, ll B) {
    if (A < 1 || B < 1) return 0;
    ll lim = min(A, B);
    ll ans = 0;
    for (ll l = 1; l <= lim; ) {
        ll a = A / l, b = B / l;
        ll r = min({lim, A / a, B / b});
        ans += (Mpref[r] - Mpref[l - 1]) * a * b;
        l = r + 1;
    }
    return ans;
}
 
// Pairs in the rectangle [L1, R1] x [L2, R2] by inclusion-exclusion on prefixes.
ll count_rect(ll L1, ll R1, ll L2, ll R2) {
    return count_coprime(R1, R2) - count_coprime(L1 - 1, R2)
         - count_coprime(R1, L2 - 1) + count_coprime(L1 - 1, L2 - 1);
}
 
int main() {
    int q;
    if (!(cin >> q)) return 0;
    vector<array<ll, 4>> qs(q);
    ll maxv = 1;
    for (auto& z : qs) {
        cin >> z[0] >> z[1] >> z[2] >> z[3];   // L1 R1 L2 R2
        maxv = max({maxv, z[1], z[3]});
    }
    build((int)maxv);
    for (auto& z : qs) cout << count_rect(z[0], z[1], z[2], z[3]) << "\n";
    return 0;
}

Two details matter. First, a * b is computed in long long: with a and b near 10^7, the product is near 10^14, which does not fit in a 32-bit int. Second, Mpref has size N + 1, so the index r never goes past the sieve, because r <= min(A, B) and the sieve covers the largest bound.

Testing the program

We tested it in three ways:

The divisor identity sum of mu(d) over d dividing n = [n = 1] for n up to 3000: 0 mismatches.
The linear sieve against direct factorisation for every n up to 10^6: 0 mismatches.
count_coprime against a brute-force double loop on 3000 random A, B below 300, and count_rect against brute force on 3000 random rectangles inside 200 by 200: 0 mismatches in both.

The program takes about 0.3 seconds on the WSL2 machine used to write this lesson, including the sieve up to 10^7 and two queries. Your time will differ with your machine.

Python version

Python is fast enough for small demonstrations, such as the table above, but not for a sieve up to 10^7 inside a time limit. This program prints the table of mu and the 10 by 10 count. It needs no input.

Python · editable

Output from the run:

mu(1..30): [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1]
coprime pairs in [1..10]x[1..10] by mu: 63
brute force: 63

Complexity

The sieve costs O(N) time and O(N) memory for N = max bound. Each query costs O(sqrt(A) + sqrt(B)) with the block grouping. With N = 10^7 the arrays take about 130 MB: 40 MB for mu as int, 80 MB for Mpref as long long, and 10 MB for the composite flags. Check the memory limit of your judge before you use this size.

Common mistakes

Missing stop in the sieve. The symptom is mu values that are non-zero for numbers with a square factor. Practice 5 shows the first one. Keep the break when i % p == 0.

Off-by-one in the subtracted range. The symptom is an answer that is too large by the count of the first row or column. The rectangle formula subtracts coprime(L1 - 1, R2) and coprime(R1, L2 - 1). Use L1 - 1 and L2 - 1, not L1 and L2. When L1 = 1, the subtracted value is coprime(0, ...), which must return 0.

Overflow in the product. The symptom is a negative or too small answer for large bounds. a * b with both near 10^7 needs long long. Check the type of every variable in the product.

Mobius with mu(1) wrong. The symptom is an answer that is too small by exactly A * B, because the d = 1 term is the largest one and it disappears when mu(1) is 0.

Trusting an AI draft without a brute-force check. A draft can be right on the 10 by 10 grid and still be wrong on rectangles with L1 > 1, because the errors sit in the subtraction. Test a rectangle with L1 > 1 and L2 > 1 against brute force before you trust it.

Checklist to keep

Write the count as a sum over divisors, then ask which function gives the sum a clean form.
Use the Mobius table: mu(1) = 1, zero for square factors, otherwise the sign of the prime count.
Use long long for every product of two counts.
Subtract L - 1, never L, and make sure a bound of 0 returns 0.
Check the sieve size against the largest bound in the input.
Test on 10 by 10 by hand and on random small inputs against brute force.

Summary

Multiplicative functions take a product over coprime parts, and the Mobius function is the one whose divisor sums vanish except at 1. Inversion lets you count pairs with exactly gcd 1 from counts of pairs that share a divisor. The linear sieve computes mu in O(N), and the block grouping makes each query fast. The test that matters most is a brute-force check on small rectangles with L > 1.

Practice

Use this prompt when you ask an AI assistant for this kind of code, then check its answer against the tests above.

Write a C++17 program that answers Q queries. Each query gives L1 R1 L2 R2 with values up to 10^7.
Print the number of pairs (x, y) with L1 <= x <= R1, L2 <= y <= R2 and gcd(x, y) = 1.
Use the Mobius function sieved in linear time and inclusion-exclusion on the prefix counts.
Use long long for all products. Explain the formula you use in two sentences.

A good answer sieves mu once, uses the four-term inclusion-exclusion, has no double loop over the pairs, and uses long long. Check it on the sample above and on 3000 random small rectangles against a brute-force loop.

Practice 1: Compute mu by hand

Find mu(36), mu(60) and mu(7 * 11).

Show the answer

mu(36) = 0 because 36 = 2^2 * 3^2 has a square factor. mu(60) = 0 because 60 = 2^2 * 3 * 5. mu(77) = 1 because 77 = 7 * 11 has two different primes.

Practice 2: Count coprime pairs in the 10 by 10 grid

Use the table in this lesson to get the number of pairs (x, y) with 1 <= x, y <= 10 and gcd 1. Then check your count with a brute-force loop.

Hint: the terms with mu(k) = 0 vanish, so only k = 1, 2, 3, 5, 6, 7, 10 matter.

Show the answer

The answer is 63. The terms are 100, -25, -9, -4, +1, -1 and +1, which sum to 63. The brute-force count also gives 63.

Practice 3: Count pairs with gcd exactly k

For A = 10, B = 10 and k = 2, count the pairs (x, y) with 1 <= x, y <= 10 and gcd exactly 2. Explain how the answer relates to coprime(5, 5).

Hint: write x = 2x' and y = 2y'. Which values can x' and y' take?

Show the answer

The answer is 19. Each pair with gcd exactly 2 has the form (2x', 2y') with 1 <= x', y' <= 5 and gcd(x', y') = 1. So the count equals coprime(5, 5), which is 19. In general, the number of pairs with gcd exactly k is coprime(A / k, B / k) with integer division.

Practice 4: Change the program to a single prefix query

Modify count_rect so it answers the question "pairs with x <= A and y <= B and gcd 1" when a query gives only A and B. Then explain why the rectangle version needs four calls.

Hint: the function count_coprime already does this, so the work is in main.

Show the answer

Read two numbers per query and call count_coprime(A, B) directly. The rectangle version needs four calls because each prefix count includes the rows and columns that start below L1 or L2. Inclusion-exclusion removes those and adds back the overlap once.

Practice 5: Find the bug in a sieve without the stop

Remove the line if (i % p == 0) { mu[i * p] = 0; break; } from build, keep the other lines, and compare mu with the trial-division check for every n up to 10^6. Report the first wrong value.

Hint: consider n = 4. It is reached as 2 * 2, and the program then needs to set it to 0.

Show the answer

The first wrong value is at n = 4. Without the stop, the code sets mu(4) = -mu(2) = 1, but mu(4) must be 0. Restore the stop and the test reports 0 mismatches.