v. Arithmetic Functions and Möbius

Arithmetic functions $f:\mathbb{N}\to \mathbb{C}$ and the Dirichlet convolution $(f\ast g)(n)={\sum }_{d\mid n}f(d)g(n/d)$ turn most divisor identities into one-line algebra. A function is multiplicative if $f(1)=1$ and $f(ab)=f(a)f(b)$ for coprime $a,b$ (completely multiplicative: for all $a,b$); it is then determined by its values on prime powers and can be sieved in $O(n)$ (Sieves). Sums up to $10^{11}$ use the harmonic lemma and Du’s sieve (Floor Sums, Sublinear Sieves).

Function	Definition	$f(p^k)$	Type
$\epsilon (n)$	$[n=1]$ (identity of $\ast$)	$0$	completely multiplicative
$1(n)$	$1$	$1$	completely multiplicative
${\mathrm{Id}}_s(n)$	$n^s$	$p^{sk}$	completely multiplicative
$\phi (n)$	$\#\{1\le k\le n:\gcd (k,n)=1\}$	$p^{k-1}(p-1)$	multiplicative
$\mu (n)$	$(-1{)}^{\#\text{primes}}$ if squarefree, else 0	$-1$ if $k=1$, $0$ if $k\ge 2$	multiplicative
$d(n)={\sigma }_0(n)$	number of divisors	$k+1$	multiplicative
${\sigma }_s(n)$	${\sum }_{d\mid n}{d}^s$	$\frac{p^{s(k+1)}-1}{p^s-1}$	multiplicative
$\omega (n)$, $\Omega (n)$	distinct prime factors / with multiplicity	$1$ / $k$	additive
$\text{rad}(n)$	product of the distinct primes	$p$	multiplicative
$s(n)=\sigma (n)-n$	aliquot sum (proper divisors)	—	—

The Dirichlet algebra

Identity	Meaning
$\mu \ast 1=\epsilon$	${\sum }_{d\mid n}\mu (d)=[n=1]$
$\phi \ast 1=\mathrm{Id}$	${\sum }_{d\mid n}\phi (d)=n$
$\mathrm{Id}\ast \mu =\phi$	$\phi (n)={\sum }_{d\mid n}\mu (d)\frac{n}{d}$
$1\ast 1=d$, $\mathrm{Id}\ast 1=\sigma$	divisor count and sum
${\mathrm{Id}}_k\ast 1={\sigma }_k$	power sums of divisors
Möbius inversion	$g=f\ast 1⟺f=g\ast \mu$
”over multiples” inversion	$g(n)={\sum }_{n\mid m\le N}f(m)⟺f(n)={\sum }_{n\mid m\le N}\mu (m/n)g(m)$
gcd sum	${\sum }_{k=1}^n\gcd (k,n)={\sum }_{d\mid n}d\phi (n/d)=(\mathrm{Id}\ast \phi )(n)$
coprime residue sum	${\sum }_{k\le n,\gcd (k,n)=1}k=\frac{n\phi (n)}{2}$ for $n>1$
small facts	$\phi (n)$ even for $n>2$; $\phi (2n)=2\phi (n)$ ($n$ even), $\phi (n)$ ($n$ odd)

Proof: the algebra, and the main identities

Convolution is commutative and associative (both sides of $(f\ast g)\ast h$ sum $f(a)g(b)h(c)$ over $abc=n$), $\epsilon$ is the identity, and the convolution of multiplicative functions is multiplicative (divisors of $mn$ with $\gcd (m,n)=1$ factor uniquely as $d_1{d}_2$, $d_1\mid m$, $d_2\mid n$). $\mu \ast 1=\epsilon$: both multiplicative, and on $p^k$ ($k\ge 1$) the sum is $1-1=0$. Hence Möbius inversion: $g=f\ast 1\Rightarrow g\ast \mu =f\ast (1\ast \mu )=f$, and conversely. The “multiples” form is the same argument on the divisibility order reversed (or Möbius inversion on the poset, Inclusion–Exclusion). $\phi \ast 1=\mathrm{Id}$: classify $k\in [1,n]$ by $d=\gcd (k,n)$: then $k/d$ ranges over the residues coprime to $n/d$, so the class has $\phi (n/d)$ elements and the classes sum to $n$; inversion gives $\phi =\mathrm{Id}\ast \mu$, and evaluating the multiplicative function on prime powers gives $\phi (p^k)=p^k-p^{k-1}$, hence $\phi (n)=n{\prod }_{p\mid n}(1-1/p)$. gcd sum: the same classification weights each class by $d$. Coprime residues: $k\mapsto n-k$ pairs the coprime residues ($n>2$), each pair summing to $n$. Evenness: for $n>2$ the pairing $k\leftrightarrow n-k$ has no fixed point ($k=n/2$ is not coprime to $n$). $\phi (2n)$ follows from multiplicativity and $\phi (2^{a+1})=2\phi (2^a)$ for $a\ge 1$.

Computing $\phi$, $\mu$, $d$, $\sigma$

ll phiOf(ll n) {                                           // O(sqrt n)
    ll r = n;
    for (ll p = 2; p * p <= n; p++) if (n % p == 0) { while (n % p == 0) n /= p; r -= r / p; }
    if (n > 1) r -= r / n;
    return r;
}
vector<int> phiUpTo(int n) {                               // O(n log log n); the linear sieve gives O(n)
    vector<int> ph(n + 1); iota(all(ph), 0);
    for (int i = 2; i <= n; i++) if (ph[i] == i) for (int j = i; j <= n; j += i) ph[j] -= ph[j] / i;
    return ph;
}
vector<int> muUpTo(int n) {                                // O(n log n) via mu * 1 = eps
    vector<int> mu(n + 1); if (n >= 1) mu[1] = 1;
    for (int i = 1; i <= n; i++) for (int j = 2 * i; j <= n; j += i) mu[j] -= mu[i];
    return mu;
}
template <class T> vector<T> dirichlet(const vector<T>& f, const vector<T>& g) {   // (f * g)(1..n), O(n log n)
    int n = sz(f) - 1; vector<T> h(n + 1);
    for (int i = 1; i <= n; i++) for (int j = i, k = 1; j <= n; j += i, k++) h[j] += f[i] * g[k];
    return h;
}

Divisor count and sum for all $n\le N$: loop over multiples (Sieves); for one $n$, factor and use the product formulas, or enumerate divisors from the factorisation (Factorization).

$n\le$	$10^3$	$10^6$	$10^9$	$10^{12}$	$10^{18}$
max $d(n)$	32 (840)	240 (720 720)	1344 (735 134 400)	6720	103 680

Average order: $\frac{1}{N}{\sum }_{n\le N}d(n)=\ln N+O(1)$, $\frac{1}{N}\sum \sigma (n)\approx \frac{{\pi }^2}{12}N$, and $\frac{1}{N^2}{\sum }_{n\le N}\phi (n)\to \frac{3}{{\pi }^2}$ (the density of coprime pairs is $6/{\pi }^2$).

Counting with $\mu$ and $\phi$

The workhorse: $[\gcd (i,j)=1]={\sum }_{d\mid \gcd (i,j)}\mu (d)$; swap the order of summation and group equal values of $\lfloor n/d\rfloor$ (at most $2\sqrt{n}$ blocks).

Quantity	Formula
coprime pairs $i\le n,j\le m$	${\sum }_d\mu (d)\lfloor n/d\rfloor \lfloor m/d\rfloor$
pairs with $\gcd =k$	the same with $n/k$, $m/k$
${\sum }_{i,j\le n}\gcd (i,j)$	${\sum }_d\phi (d)\lfloor n/d{\rfloor }^2$
${\sum }_{i,j\le n}\text{lcm}(i,j)$	${\sum }_{d}d{\sum }_e\mu (e)e^{2}S(\lfloor n/de\rfloor {)}^2$, $S(x)=x(x+1)/2$
squarefree numbers $\le n$	${\sum }_{d\le \sqrt{n}}\mu (d)\lfloor n/d^2\rfloor$
fractions in lowest terms $p/q$, $1\le p\le q\le n$ (Farey length)	$\Phi (n)={\sum }_{i\le n}\phi (i)$
lattice points visible from the origin in $[1,n{]}^2$	$2\Phi (n)-1$
integers $\le n$ divisible by none of $p_1,\dots ,p_k$	inclusion–exclusion over subsets = $\mu$ restricted to those primes
ordered pairs $(a,b)$ with $\gcd =X$, $\text{lcm}=Y$	$2^{\#\{p:v_p(X)<v_p(Y)\}}$ if $X\mid Y$, else 0
${\sum }_{i=1}^n\sigma (i)={\sum }_{d\le n}d\lfloor n/d\rfloor$	blocks: $O(\sqrt{n})$
${\sum }_{i\le n}d(i)={\sum }_{d\le n}\lfloor n/d\rfloor =2{\sum }_{i\le \sqrt{n}}\lfloor n/i\rfloor -\lfloor \sqrt{n}{\rfloor }^2$	hyperbola method

ll coprimePairs(ll n, ll m, const vector<ll>& preMu) {    // preMu[x] = sum_{d <= x} mu(d), x >= min(n, m)
    ll res = 0;
    for (ll l = 1, r; l <= min(n, m); l = r + 1) { r = min(n / (n / l), m / (m / l)); res += (preMu[r] - preMu[l - 1]) * (n / l) * (m / l); }
    return res;
}
ll sumSigmaMod(ll n, ll M) {                               // sum_{i <= n} sigma(i) mod M = sum_d d * floor(n/d)
    auto tri = [&](ll a, ll b) { i128 s = (i128)(a + b) * (b - a + 1) / 2; return (ll)(s % M); };   // a + ... + b
    ll res = 0;
    for (ll l = 1, r; l <= n; l = r + 1) { r = n / (n / l); res = (res + (i128)tri(l, r) * ((n / l) % M)) % M; }
    return res;
}
ll gcdLcmPairs(ll X, ll Y) {                               // ordered (a, b) with gcd X and lcm Y
    if (Y % X) return 0;
    ll q = Y / X, c = 0;                                   // primes where the exponents differ are those of Y / X
    for (ll p = 2; p * p <= q; p++) if (q % p == 0) { c++; while (q % p == 0) q /= p; }
    if (q > 1) c++;
    return 1LL << c;
}

Proof: coprime pairs, gcd / lcm sums, squarefree count, hyperbola, gcd–lcm pairs

Coprime pairs: ${\sum }_{i,j}{\sum }_{d\mid i,d\mid j}\mu (d)={\sum }_d\mu (d)\lfloor n/d\rfloor \lfloor m/d\rfloor$. gcd sum: $\gcd (i,j)={\sum }_{d\mid \gcd }\phi (d)$ by $\phi \ast 1=\mathrm{Id}$, then swap sums. lcm sum: write $\text{lcm}=ij/\gcd$, set $i=d{i}^{\prime },j=d{j}^{\prime }$ with $\gcd (i^{\prime },j^{\prime })=1$, remove the coprimality with $\mu (e)$ and substitute $i^{\prime }=e{i}^{\prime \prime }$, $j^{\prime }=e{j}^{\prime \prime }$. Squarefree: $[n\text{squarefree}]={\sum }_{d^2\mid n}\mu (d)$ (multiplicative check on $p^k$: $1$ for $k\le 1$, $1-1=0$ for $k\ge 2$); sum over $n$. Blocks: for $l\le n$, $\lfloor n/x\rfloor$ is constant for $x\in [l,\lfloor n/\lfloor n/l\rfloor \rfloor ]$, and there are at most $2\sqrt{n}$ distinct values (either $x\le \sqrt{n}$ or the value is $\le \sqrt{n}$). Hyperbola: ${\sum }_{n\le N}d(n)$ counts lattice points $ab\le N$; count those with $a\le \sqrt{N}$ or $b\le \sqrt{N}$ and subtract the doubly counted square. $\sum \sigma$: ${\sum }_{i\le n}{\sum }_{d\mid i}d={\sum }_{d}d\lfloor n/d\rfloor$. gcd–lcm: prime by prime, $\{v_p(a),v_p(b)\}=\{v_p(X),v_p(Y)\}$, which gives 2 choices when the exponents differ and 1 when equal, and $X\mid Y$ is necessary.

Euler’s theorem and power towers

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ for $\gcd (a,n)=1$, so exponents reduce modulo $\phi (n)$ (or the Carmichael $\lambda (n)$). Without coprimality, for $k\ge {\log }_{2}n$: $a^k\equiv a^{(k\mathrm{mod}\phi (n))+\phi (n)}(\mathrm{mod}n)$. Power towers $a_1^{a_2^{a_3^{\cdots }}}\mathrm{mod}n$ recurse on $\phi (n),\phi (\phi (n)),\dots$, which reaches 1 within $O(\log n)$ steps.

pair<ll, bool> powCap(ll a, ll e, ll m) {                 // {a^e mod m, a^e >= m}
    ll r = 1 % m; bool big = false; ll x = a % m; bool xbig = a >= m;
    for (; e; e >>= 1) {
        if (e & 1) { big = big || xbig || (i128)r * x >= m; r = (i128)r * x % m; }   // conservative flag
        if (e > 1) { xbig = xbig || (i128)x * x >= m; x = (i128)x * x % m; }
    }
    return {r, big};
}
pair<ll, bool> tower(const vector<ll>& a, int i, ll m) {  // a[i]^(a[i+1]^...) mod m, flag: value >= m
    if (i == sz(a)) return {1 % m, 1 >= m};
    if (m == 1) { auto [_, b] = tower(a, i + 1, 1); (void)_; return {0, true}; }
    ll ph = phiOf(m); auto [e, ebig] = tower(a, i + 1, ph);
    if (ebig) e += ph;                                     // generalized Euler: only when the true exponent is >= phi
    auto [v, vbig] = powCap(a[i], e, m);
    return {v, vbig || (ebig && a[i] >= 2)};
}

The “big” flags are needed because the shift by $\phi (n)$ is only valid when the true exponent is large; with exponent below ${\log }_{2}n$ the plain value must be used. (A simpler, common bound: treat the exponent as large when the tower above has at least one element $\ge 2$ and the partial value exceeds $\phi$.)

Proof: the generalised Euler theorem

Write $n=\prod p_i^{e_i}$ and fix $p^e\Vert n$. If $p\nmid a$, Euler gives $a^{\phi (p^e)}\equiv 1(\mathrm{mod}{p}^e)$, and $\phi (p^e)\mid \phi (n)$, so both sides agree modulo $p^e$. If $p\mid a$, then $a^k\equiv 0(\mathrm{mod}{p}^e)$ whenever $k\ge e$, and both exponents qualify: $k\ge {\log }_{2}n\ge e$, and $(k\mathrm{mod}\phi (n))+\phi (n)\ge \phi (n)\ge \phi (p^e)=p^{e-1}(p-1)\ge e$. CRT combines the prime powers. The chain $\phi (\phi (\cdots ))$ halves at least every two steps ($\phi (n)$ is even for $n>2$ and $\phi (m)\le m/2$ for even $m$), so the recursion depth is $O(\log n)$.

Prefix sums for huge $n$: Du’s sieve

If $f\ast g=h$ and prefix sums of $g$ and $h$ are easy, then $S_f(n)={\sum }_{i\le n}f(i)$ satisfies $g(1)S_f(n)=S_h(n)-{\sum }_{d=2}^{n}g(d)S_f(\lfloor n/d\rfloor )$. Sieve $S_f$ up to $n^{2/3}$ and memoise the rest: $O(n^{2/3})$.

Target $S_f$	$g$	$h=f\ast g$
Mertens $M(n)=\sum \mu$	$1$	$\epsilon$: $S_h=1$
$\Phi (n)=\sum \phi$	$1$	$\mathrm{Id}$: $S_h=n(n+1)/2$
$\sum \mu (i)i$	$\mathrm{Id}$	$\epsilon$
$\sum \phi (i)i$	$\mathrm{Id}$	${\mathrm{Id}}_2$: $S_h=n(n+1)(2n+1)/6$

struct DuSieve {                                           // Phi(n) = sum phi, M(n) = sum mu, n up to ~1e11 (values mod 2^64 for Phi)
    int L; vector<ll> sphi, smu; unordered_map<ll, ll> cphi, cmu;
    DuSieve(ll nmax) {
        L = max(10, (int)cbrtl((long double)nmax * nmax)); sphi.assign(L + 1, 0); smu.assign(L + 1, 0);
        vector<int> ph(L + 1), mu(L + 1), pr; vector<char> comp(L + 1); ph[1] = mu[1] = 1;
        for (int i = 2; i <= L; i++) {
            if (!comp[i]) pr.push_back(i), ph[i] = i - 1, mu[i] = -1;
            for (int p : pr) { if ((ll)i * p > L) break; comp[i * p] = 1; if (i % p == 0) { ph[i * p] = ph[i] * p; mu[i * p] = 0; break; } ph[i * p] = ph[i] * (p - 1); mu[i * p] = -mu[i]; }
        }
        for (int i = 1; i <= L; i++) sphi[i] = sphi[i - 1] + ph[i], smu[i] = smu[i - 1] + mu[i];
    }
    ll Phi(ll n) {
        if (n <= L) return sphi[n];
        if (auto it = cphi.find(n); it != cphi.end()) return it->second;
        ll r = (ll)((i128)n * (n + 1) / 2);
        for (ll l = 2, rr; l <= n; l = rr + 1) { rr = n / (n / l); r -= (rr - l + 1) * Phi(n / l); }
        return cphi[n] = r;
    }
    ll M(ll n) {
        if (n <= L) return smu[n];
        if (auto it = cmu.find(n); it != cmu.end()) return it->second;
        ll r = 1;
        for (ll l = 2, rr; l <= n; l = rr + 1) { rr = n / (n / l); r -= (rr - l + 1) * M(n / l); }
        return cmu[n] = r;
    }
};

Proof: Du's recurrence and its cost

$S_h(n)={\sum }_{k\le n}{\sum }_{d\mid k}g(d)f(k/d)={\sum }_{d\le n}g(d){\sum }_{j\le n/d}f(j)={\sum }_{d\le n}g(d)S_f(\lfloor n/d\rfloor )$; isolate the $d=1$ term. Only values $\lfloor n/d\rfloor$ are ever requested (and $\lfloor \lfloor n/a\rfloor /b\rfloor =\lfloor n/ab\rfloor$), so there are $O(\sqrt{n})$ distinct states. A state $x>L$ costs $O(\sqrt{x})$ by blocks; summing over $x=n/d$ for $d<n/L$ gives ${\sum }_{d\le n/L}\sqrt{n/d}=O(n/\sqrt{L})$, and the sieve costs $O(L)$; balancing at $L=n^{2/3}$ gives $O(n^{2/3})$.

Patterns

Problem	Approach
count numbers $\le N$ with exactly $k$ divisors	sieve $d$; or enumerate exponent signatures with $\prod (e_i+1)=k$
smallest number with at least $k$ divisors / highly composite numbers	DFS over non-increasing exponents of the first primes
number of divisors of a product / of $n!$	add exponents; Legendre per prime (Factorials mod p)
sum over pairs $i\mid j$	iterate multiples, $O(N\log N)$
order of $a$, primitive roots	order divides $\phi (n)$ (Primitive Roots)
necklaces with $c$ colours	$\frac{1}{n}{\sum }_{d\mid n}\phi (d)c^{n/d}$ (Burnside)
period of the decimal expansion of $1/n$	multiplicative order of 10 modulo $n$ (after removing factors 2, 5)
inverse modulo composite $m$	$a^{\phi (m)-1}$, but extended Euclid is simpler

ll smallestWithDivisors(ll k) {                            // smallest n with d(n) >= k (k up to ~1e5; n fits in ll)
    static const int P[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
    ll best = LLONG_MAX;
    auto dfs = [&](auto& self, int i, ll n, ll d, int maxE) -> void {
        if (d >= k) { best = min(best, n); return; }
        if (i == 16) return;
        ll x = n;
        for (int e = 1; e <= maxE; e++) { if ((i128)x * P[i] >= best) break; x *= P[i]; self(self, i + 1, x, d * (e + 1), e); }
    };
    dfs(dfs, 0, 1, 1, 62);
    return best;
}

Proof: exponents are non-increasing in the optimum

If $n=\prod p_i^{e_i}$ has $e_i<e_j$ for primes $p_i<p_j$, swapping the two exponents keeps $d(n)$ and makes $n$ smaller. So a minimal $n$ uses the first primes with non-increasing exponents, which is exactly what the search enumerates (and it prunes branches already at least the best found).