PrevNext
Has Not Appeared
 0/7

Prefix Sums of Multiplicative Functions

Authors: Tianqin Meng, Benjamin Qi

Covering Dirichlet convolution, Möbius inversion, and binomial inversion.

Edit This Page

Initial Overview

Definition

  1. If a function f:Z+Cf: \mathbb{Z}^+ \rightarrow \mathbb{C} maps positive integers to complex numbers, it's an arithmetic function.
  2. If f(n)f(n) is an arithmetic function, f(1)=1f(1) = 1 and f(p⋅q) = f(p)f(q)f(p) \cdot f(q) for any coprime positive integers p,q, it's a multiplicative function.
  3. If f(n)f(n) is multiplicative and f(pq)f(p \cdot q) = f(p)f(q)f(p)\cdot f(q) for any positive integers p,q, it's a completely multiplicative function.

If f(n)f(n) is a multiplicative function, then for a positive integer n=i=1kpikin = \prod_{i=1}^{k} p_i^{k_i}, we have

f(n)=i=1kf(piki)f(n) = \prod_{i=1}^{k} f(p_i^{k_i})

If f(n)f(n) is a completely multiplicative function, then for a positive integer n=i=1kpikin = \prod_{i=1}^{k} p_i^{k_i}, we have

f(n)=i=1kf(pi)kif(n) = \prod_{i=1}^{k} f(p_i)^{k_i}

Examples

Common multiplicative functions are

  • Divisor function: σk(n)=dndk\sigma_k(n) = \sum_{d|n} d^k, representing the sum of the kkth powers of divisors of nn. Note that σk(n)\sigma_k(n) and σk(n)σ^k(n) are different.
  • Divisor count function: τ(n)=σ0(n)=dn1\tau(n) = \sigma_0(n) = \sum_{d|n} 1, representing the count of divisors of nn, also denoted as d(n)d(n).
  • Divisor sum function: σ(n)=σ1(n)=dnd\sigma(n) = \sigma_1(n) = \sum_{d|n} d, representing the sum of divisors of nn.
  • Euler's totient function: φ(n)=i=1n[(n,i)=1]1\varphi(n) = \sum_{i=1}^n [(n,i)=1] \cdot 1, representing the count of positive integers less than or equal to nn and coprime to nn. Additionally, i=1n[(n,i)=1]i=\sum_{i=1}^n [(n,i)=1] \cdot i = nφ(n)+[n=1]2\frac{n\varphi(n) + [n=1]}{2}, φ(n)\varphi(n) is even.
  • Möbius function: μ(n)\mu(n), serving as the multiplicative inverse of the identity function in Dirichlet convolution, μ(1)=1\mu(1) = 1, for a square-free number n=i=1tpin = \prod_{i=1}^t p_i, μ(n)=(1)t\mu(n) = (-1)^t, and for a number with square factors, μ(n)=0\mu(n) = 0.
  • Unit function: e(n)=[n=1]e(n) = [n=1], serving as the identity element in Dirichlet convolution, completely multiplicative.
  • Constant function: I(n)=1I(n) = 1, completely multiplicative.
  • Identity function: id(n)=nid(n) = n, completely multiplicative.
  • Power function: idk(n)=nkid^k(n) = n^k, completely multiplicative.

The two classic formulas regarding the Möbius function and the Euler function are:

  • [n=1]=dnμ(d)[n=1] = \sum_{d|n} \mu(d), Interpreting μ(d)\mu(d) as the coefficients of the inclusion-exclusion principle proves it.
  • n=dnφ(d)n = \sum_{d|n} \varphi(d). To prove it, we can count the number of occurrences of 1n(1in)\frac{1}{n}(1 \leq i \leq n) in its simplest fraction form.

Dirichlet Convolution

The Dirichlet convolution of number-theoretic functions ff and gg is defined as (fg)(n)=dnf(d)g(nd)(f*g)(n) = \sum_{d|n} f(d) \cdot g(\frac{n}{d}). Dirichlet convolution satisfies commutativity, associativity, and distributivity with respect to addition. There exists an identity function e(n)=[n=1]e(n) = [n=1] such that fe=f=eff*e = f = e*f。If ff and gg are multiplicative functions, then fgf*g is also multiplicative.

A common technique with Dirichlet convolution involves dealing with the convolution of a multiplicative function ff and the identity function II. For example, if n=i=1tpikin = \prod_{i=1}^{t} p_i^{k_i} and g(n)=dnf(d)g(n) = \sum_{d|n} f(d),then we have

g(n)=i=1tj=0kif(pij)g(n) = \prod_{i=1}^{t} \sum_{j=0}^{k_i} f(p_i^j)

Möbius Inversion

Möbius inversion is also a discussion regarding g(n)=dnf(d)g(n) = \sum_{d|n} f(d) , but it does not require ff to be multiplicative and is applicable in cases where g(n)g(n) is known and f(n)f(n) is to be determined.

Since Iμ=eI \cdot \mu = egμ=fIμ=fe=fg \cdot \mu = f \cdot I \cdot \mu = f \cdot e = f,and f(n)=dng(d)μ(nd)f(n) = \sum_{d|n} g(d) \cdot \mu\left(\frac{n}{d}\right). Similarly, g(n)=ndf(d)f(n)=ndg(d)μ(dn)g(n) = \sum_{n|d} f(d) \rightarrow f(n) = \sum_{n|d} g(d) \cdot \mu\left(\frac{d}{n}\right)

Example - Sum of Divisors

Focus Problem – try your best to solve this problem before continuing!

Explanation

It's not feasible to compute directly, but we can derive it as follows:

i=1nσ(i)=i=1nj=1n[ji]j=i=1nij=1n[ij]=i=1nini\sum_{i=1}^{n}\sigma(i)=\sum_{i=1}^{n}\sum_{j=1}^{n}[j|i]\cdot j=\sum_{i=1}^{n}i\cdot\sum_{j=1}^{n}[i|j]=\sum_{i=1}^{n}i\cdot\left\lfloor\frac{n}{i}\right\rfloor

When ini \leq \sqrt{n}, there are only O(n)O(\sqrt{n}) distinct values for ni\left\lfloor\frac{n}{i}\right\rfloor. Similarly, when i>ni > \sqrt{n}, ni<n\left\lfloor\frac{n}{i}\right\rfloor < n has only O(n)O(\sqrt{n}) distinct values. For a fixed ni\left\lfloor\frac{n}{i}\right\rfloor, the values of ii form a contiguous interval, which is [nni+1+1,nni]\left[\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor+1}\right\rfloor+1,\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor\right]. Therefore, the calculation can be done in O(n)O(\sqrt{n}) time.

Similarly, the sum of the number of divisors for the first nn positive integers can be calculated in the same manner. I leave this as an exercise for the reader.

Another thing to note is that i=1nnii=i=1nni(ni+1)2\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor\cdot i=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor\cdot\frac{(\left\lfloor\frac{n}{i}\right\rfloor+1)}{2}. This is also a common representation form.

Implementation

Time Complexity: O(n)\mathcal{O}(\sqrt{n})

C++

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n; // Taking input for n
long long sum = 0;
int i; // Initializing i globally to keep its value after the loop
for (i = 1; i * i <= n; i++) {

Example - Totient Sum

Focus Problem – try your best to solve this problem before continuing!

Explanation

Currently, the formulas related to Euler's totient function mentioned in this article are limited. Can we use them to simplify the problem? The answer is yes, and now we'll utilize the formula dnφ(d)=n\sum_{d|n}\varphi(d)=n to simplify the expression.

This formula can also be seen as φ(n)=ndn,d<nφ(d)\varphi(n)=n-\sum_{d|n, d<n}\varphi(d). Let's denote ϕ(n)=i=1nφ(i)\phi(n)=\sum_{i=1}^n \varphi(i), then we have:

ϕ(n)=i=1nφ(i)=i=1nidi,d<iφ(d)=n(n+1)2i=2ndi,d<iφ(d)=n(n+1)2i=2nd=1n(id)φ(d)\phi(n)=\sum_{i=1}^n\varphi(i)=\sum_{i=1}^n i−\sum_{d|i,d<i}\varphi(d)=\frac{n\cdot(n+1)}{2}−\sum_{i=2}^n\sum_{d|i,d<i}\varphi(d)=\frac{n\cdot(n+1)}{2}−\sum_{i=2}^{n}\sum_{d=1}^{\left\lfloor\frac{n}{\left(\frac{i}{d}\right)}\right\rfloor}\varphi(d)
n(n+1)2i=2nd=1niϕ(d)=n(n+1)2i=2nϕ(ni)n \cdot \frac{(n+1)}{2} - \sum_{i=2}^{n} \sum_{d=1}^{\lfloor \frac{n}{i} \rfloor} \phi(d) = n \cdot \frac{(n+1)}{2} - \sum_{i=2}^{n} \phi(\lfloor \frac{n}{i} \rfloor)

So as long as you calculate the values of ϕ(ni\phi(\lfloor \frac{n}{i} \rfloor) for O(n)O(\sqrt{n}) times, you can compute ϕ(n)\phi(n). What about the complexity of such an operation?

Suppose the complexity of calculating ϕ(n)\phi(n) is T(n)T(n), then we have T(n)=O(n)+i=1nT(i)+T(n/i)T(n) = O(\sqrt{n}) + \sum_{i=1}^{\sqrt{n}} T(i) + T(n/i). Here, we only expand one layer because deeper complexities are higher-order terms. So, we have T(n)=i=1nO(i)+O(ni)=O(n3/4)T(n) = \sum_{i=1}^{\sqrt{n}} O(\sqrt{i}) + O(\sqrt{\frac{n}{i}}) = O(n^{3/4}).

Since ϕ(n)\phi(n) is a prefix sum of a multiplicative function, the sieve method can preprocess a portion. Assuming the preprocessing includes the first kk positive integers' ϕ(n)\phi(n) where knk \geq \sqrt{n}, the complexity becomes T(n)=i=1kni=O(nk)T(n) = \sum_{i=1}^{k} {\sqrt{\frac{n}{i}}} = O({\frac{n}{\sqrt{k}}}). When k=O(n2/3)k = O(n^{2/3}), we can achieve a good complexity of T(n)=O(n2/3)T(n) = O(n^{2/3}).

How did we come up with the place where we utilized φ(n)=ndn,d<nφ(d)\varphi(n) = n-\sum_{d|n,d<n} \varphi(d)? Let's take a look at this:

n(n+1)2=i=1ni=i=1nd[di]φ(d)=i=2nd=1n(id)φ(d)=i=1nϕ(ni)\frac{n \cdot (n+1)}{2} = \sum_{i=1}^{n} i = \sum_{i=1}^{n} \sum_{d} [d|i]\varphi(d) = \sum_{i=2}^{n} \sum_{d=1}^{\left\lfloor \frac{n}{\left(\frac{i}{d}\right)} \right\rfloor} \varphi(d) = \sum_{i=1}^{n} \phi(\left\lfloor \frac{n}{i} \right\rfloor)

If we can construct a function through Dirichlet convolution that computes prefix sums more efficiently and if another function suitable for convolution is also easy to calculate, we can simplify the calculation process. For example, in the above problem, we used the property of φI=id\varphi * I = id. But remember, not all problems of this type can be easily solved by just pairing with an identity function II. Sometimes, a more careful observation is needed.

Implementation

Time Complexity: O(n2/3)\mathcal{O}(n^{2/3})

C++

template <int SZ> struct Sieve {
vi pr;
int sp[SZ], phi[SZ]; // smallest prime that divides
Sieve() { // above is faster
memset(sp, 0, sizeof sp);
phi[1] = 1;
FOR(i, 2, SZ) {
if (sp[i] == 0) {
sp[i] = i, pr.pb(i);
phi[i] = i - 1;

Example - Counting Primes

Focus Problem – try your best to solve this problem before continuing!

There's two ways to do this problem. The first solution has a higher time complexity but a less complex implementation, while the second has a lower time complexity at the cost of a more complex implementation.

For a more complete explanation of these algorithms, refer to this CF blog post.

Explanation 1

Utilizes a dynamic programming approach based on a recursion relation derived from sieving.

The algorithm iteratively reduces the count of numbers that are not divisible by primes, utilizing a recursive formula. It achieves a complexity of O(N3/4logN)O(\frac{N^{3/4}}{\sqrt{\log N}}).

Implementation

Time Complexity: O(N3/4logN)O(\frac{N^{3/4}}{\sqrt{\log N}})

C++

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using ll = long long;
using std::cout;
using std::endl;
using std::pair;
using std::vector;

Explanation 2

There exists an O(n2/3logn3)O(\frac{n^{2/3}}{\sqrt[3]{\log n}}) implementation; see Maksim1744’s Codeforces blog for more details. Below is an implementation with a BIT. Note that the fastest solutions to this library checker problem look like they run in O(N3/4logN)O(\frac{N^{3/4}}{\sqrt{\log N}}).

Implementation

Time Complexity: O(n2/3logn3)O(\frac{n^{2/3}}{\sqrt[3]{\log n}})

C++

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using ll = long long;
using std::cout;
using std::endl;
using std::pair;
using std::vector;

Problems

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext