Skip to content
Tutorials Center
My learning

Topics

Lesson 188 of 225 ยท Math and Bit Manipulation

Inclusion-Exclusion, Euler's Totient and Mobius Function

Count with inclusion-exclusion, build totient and Mobius sieves in Python, count coprime pairs fast and use Mobius inversion to undo divisor sums.

Some counting questions have a simple shape: "how many numbers up to n are divisible by 2 or 3 or 5?", or "how many pairs (a, b) have gcd(a, b) = 1?". Adding up the counts for each condition double-counts the overlaps, and fixing that carefully is called inclusion-exclusion. When the conditions are "divisible by a prime", the signs follow a pattern so regular that number theorists gave it a name, the Mobius function.

In this lesson you will use inclusion-exclusion directly, sieve Euler's totient and the Mobius function for every number up to N, count coprime pairs in O(N), and learn Mobius inversion, a way to recover f from its divisor sums g(n) = sum of f(d) over d | n. You should know sieves from Sieve of Eratosthenes and divisors from number theory.

Inclusion-exclusion

For two sets, |A or B| = |A| + |B| - |A and B|. For any number of sets the pattern is: add single sets, subtract pairs, add triples, subtract quadruples, and so on.

TEXT
|A1 or ... or Am| = sum of |Ai| - sum of |Ai and Aj| + sum of |Ai and Aj and Ak| - ...

Take n = 100 and ask for numbers divisible by 2, 3 or 5. "Divisible by 2 and 3" means divisible by lcm = 6, and so on:

TEXT
100/2 + 100/3 + 100/5          = 50 + 33 + 20 = 103
- (100/6 + 100/10 + 100/15)    = -(16 + 10 + 6) = -32
+ 100/30                       = +3
total                          = 74

Looping over all 2^m subsets takes O(2^m) time, fine for a handful of primes. Bitmasks make the code short.

Python Inclusion-exclusion over subsets of primes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last helper counts numbers coprime to n: that count is Euler's totient phi(n).

Euler's totient

phi(n) is the number of integers in 1..n coprime to n. If n = p1^a1 * p2^a2 * ..., inclusion-exclusion over the distinct primes collapses to a product:

TEXT
phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ...

Three useful properties: phi is multiplicative (phi(ab) = phi(a) phi(b) when gcd(a, b) = 1), phi(p) = p - 1 for a prime p, and sum of phi(d) over d | n = n.

To get phi for all numbers up to N, run a sieve: start with phi[i] = i, and for every prime p, replace phi[m] with phi[m] - phi[m] // p for each multiple m. That costs about N log log N.

Python Totient sieve

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Mobius function

Define mu(n) by the prime factorization of n:

  • mu(1) = 1
  • mu(n) = 0 if some prime squared divides n
  • mu(n) = (-1)^k if n is a product of k distinct primes

So mu(2) = -1, mu(6) = 1, mu(4) = 0, mu(30) = -1. This is exactly the sign pattern of inclusion-exclusion over primes, which is why it appears here. Its key property:

TEXT
sum of mu(d) over all d | n  =  1 if n == 1, else 0

A linear sieve computes mu and the list of primes in O(N), by visiting each composite exactly once through its smallest prime factor.

Python Linear sieve for mu

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting coprime pairs

How many pairs (a, b) with 1 <= a, b <= n have gcd(a, b) = 1? Use the property of mu as a filter: the indicator "gcd is 1" equals the sum of mu(d) over common divisors d. Swap the order of summation and you get

TEXT
coprime_pairs(n) = sum for d = 1..n of  mu(d) * floor(n/d)^2

That is an O(n) loop once mu is known. Grouping equal values of n // d brings it down to about O(sqrt(n)) terms with a prefix sum of mu. A second formula uses the totient: ordered pairs (a, b) with a <= b number sum of phi(b), so the ordered total is 2 * sum of phi(k) for k = 1..n - 1.

Python Coprime pairs three ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratio approaches 6 / pi^2, about 60.8 percent: a classic fact that two random numbers are coprime with that probability.

Mobius inversion

Suppose you know the divisor sums g(n) = sum of f(d) over d | n and want f back. Mobius inversion says:

TEXT
f(n) = sum of mu(n / d) * g(d) over d | n

Example: the divisor sums of phi are g(n) = n, so phi(n) = sum of mu(n/d) * d. In code, you can invert with a sieve-like loop, subtracting each value from its multiples. This is the same trick as a "difference array" over the divisor lattice.

Python Recover f from its divisor sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity of the sieves, the pair counts and the inversion is O(N log N) or better, so a limit of a few million is comfortable even in Python.

When to use what

Task Tool
Count numbers divisible by any of a few given values inclusion-exclusion over subsets, O(2^m)
phi for one n factor n, apply the product formula
phi or mu for every number up to N sieve, O(N log log N) or O(N)
Count pairs with gcd = 1 or gcd = g sum of mu(d) * floor(n/d)^2
Recover f from divisor sums Mobius inversion in O(N log N)

Common mistakes: forgetting that mu(n) = 0 for numbers with a squared prime factor, mixing up gcd = 1 and "no common divisor greater than 1" in off-by-one counts ((1, 1) is a coprime pair), and iterating d in decreasing order in the inversion loop.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many integers from 1 to 100 are divisible by 2, 3 or 5?

    Add the singles (103), subtract the pairs (32), add back the triple (3): 74. The other 26 numbers are coprime to 30.
  2. 2. What is mu(12)?

    12 = 2^2 * 3 has a squared prime factor, so mu(12) = 0.
  3. 3. What is phi(36)?

    36 = 2^2 * 3^2, so phi = 36 * (1/2) * (2/3) = 12.
  4. 4. Which formula counts ordered pairs (a, b) in 1..n with gcd(a, b) = 1?

    The sum of mu(d) over common divisors d of a and b is 1 exactly when gcd(a, b) = 1. Swapping the sums leaves floor(n/d) choices for each of a and b.

Summary

  • Inclusion-exclusion adds singles, subtracts pairs, adds triples and so on; with m conditions it needs 2^m terms.
  • phi(n) = n * product of (1 - 1/p) over distinct primes p of n; sieve it for all n in about N log log N.
  • mu(n) is 0 with a squared prime, otherwise (-1)^(number of distinct primes); a linear sieve computes it in O(N).
  • Coprime pairs: sum of mu(d) * floor(n/d)^2, or 2 * (phi(1) + ... + phi(n)) - 1.
  • Mobius inversion recovers f from divisor sums g, in the same sieve style.

Next: Primitive Roots and Discrete Logarithm