Exercise · ZW-MOBIUS-INVERSION-FORMULA-009 · ★★★ Advanced
Let \(g(n)=n\) for all \(n\). What is \(f(12)\) by Möbius inversion?
Choose one option.
Show answer
- C. 4
Explanation
With nonzero \(\mu(d)\) at \(d=1,2,3,6\), the sum is \(12-6-4+2=4\), which matches \(\varphi(12)\). The terms with \(d=4\) and \(d=12\) vanish because \(\mu\) is zero there.
Review the concept: Möbius inversion formula
Formula that recovers an arithmetic function \(f\) from its sum over divisors, using the Möbius function \(\mu\).
\[f(n)=\sum_{d\mid n}\mu(d)\,g\!\left(\frac{n}{d}\right)\]
More practice problems: möbius inversion formula
- ZW-MOBIUS-INVERSION-FORMULA-001 Which arithmetic function appears as the coefficient in the Möbius inversion formula?
- ZW-MOBIUS-INVERSION-FORMULA-002 What is the correct way to invert g(n)=∑_d| nf(d)?
- ZW-MOBIUS-INVERSION-FORMULA-003 Over which set is the sum taken in g(n)=∑_d| nf(d)?
- ZW-MOBIUS-INVERSION-FORMULA-004 If g(n)=∑_d| nμ(d) for every n, what is g(12)?
- ZW-MOBIUS-INVERSION-FORMULA-005 What is μ(4)?
- ZW-MOBIUS-INVERSION-FORMULA-006 If g(n)=n for all n, compute f(6) using Möbius inversion.
- ZW-MOBIUS-INVERSION-FORMULA-007 If g(n)=n^2 for all n, compute f(3) using Möbius inversion.
- ZW-MOBIUS-INVERSION-FORMULA-008 If g(n)=∑_d| nf(d) and f(n)=n for all n, compute g(4).
← ZW-MOBIUS-INVERSION-FORMULA-008 ZW-MOBIUS-INVERSION-FORMULA-010 →