Prefix Sums of Multiplicative Functions

Prerequisite Skills

Definition of multiplicative functions

1. If a function f(n) maps positive integers to complex numbers (f: ℤ⁺ → ℂ), it's an arithmetic function.
2. If f(n) is an arithmetic function, f(1) = 1 and f(p⋅q) = f(p)⋅f(q) for any coprime positive integers p,q, it's a multiplicative function.
3. Further, if f(n) is multiplicative and f(p⋅q) = f(p)⋅f(q) for any positive integers p,q, it's a completely multiplicative function.

Properties and Examples of Multiplicative Functions

1. Common multiplicative functions are

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

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

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

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

Dirichlet Convolution and Möbius Inversion

1. The Dirichlet convolution of number-theoretic functions $f$ and $g$ is defined as $(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]$ such that $f*e = f = e*f$。If $f$ and $g$ are multiplicative functions, then $f*g$ is also multiplicative.

2. A common technique with Dirichlet convolution involves dealing with the convolution of a multiplicative function $f$ and the identity function $I$. For example, if $n = \prod_{i=1}^{t} p_i^{k_i}$ and $g(n) = \sum_{d|n} f(d)$，then：$g(n) = \prod_{i=1}^{t} \sum_{j=0}^{k_i} f(p_i^j)$

3. Möbius inversion is also a discussion regarding $g(n) = \sum_{d|n} f(d)$ , but it does not require $f$ to be multiplicative and is applicable in cases where $g(n)$ is known and $f(n)$ is to be determined. Since $I*\mu = e$， $g*\mu = f*I*\mu = f*e = f$，and $f(n) = \sum_{d|n} g(d) \cdot \mu\left(\frac{n}{d}\right)$. Similarly, $g(n) = \sum_{n|d} f(d) \Rightarrow f(n) = \sum_{n|d} g(d) \cdot \mu\left(\frac{d}{n}\right)$，Binomial inversion is also a similar technique. An example illustrates the relationship between the Euler function and the Möbius function: since $\sum_{d|n} \varphi(d) = n$，then $\varphi(n) = \sum_{d|n} \mu(d) \cdot \frac{n}{d}$，which implies $\frac{\varphi(n)}{n} = \sum_{d|n} \frac{\mu(d)}{d}$

Focus problem # 1

Find the sum of divisors of the first $n$ positive integers, i.e., $\sum_{i=1}^n \sigma(i)$, where $n \leq 10^{12}$.

Approach:

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

When $i \leq \sqrt{n}$, there are only $O(\sqrt{n})$ distinct values for $\left\lfloor\frac{n}{i}\right\rfloor$. Similarly, when $i > \sqrt{n}$, $\left\lfloor\frac{n}{i}\right\rfloor < n$ has only $O(\sqrt{n})$ distinct values. For a fixed $\left\lfloor\frac{n}{i}\right\rfloor$, the values of $i$ form a contiguous interval, which is $\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(\sqrt{n})$ time.

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

Another thing to note is that $\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.

Focus problem # 2

Now let's increase the difficulty a bit. We want to find the sum of Euler's totient function for the first $n$ positive integers, i.e., $\sum_{i=1}^{n} \varphi(i)$, where $n \leq 10^{11}$.

Approach:

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 $\sum_{d|n}\varphi(d)=n$ to simplify the expression.

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

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

Suppose the complexity of calculating $\phi(n)$ is $T(n)$, then we have $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) = \sum_{i=1}^{\sqrt{n}} O(\sqrt{i}) + O(\sqrt{\frac{n}{i}}) = O(n^{3/4})$.

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

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

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 $\varphi * I = id$. But remember, not all problems of this type can be easily solved by just pairing with an identity function $I$. Sometimes, a more careful observation is needed.

More information below left over by Benjamin Qi

https://codeforces.com/blog/entry/54150

Linear Time Sieve

https://judge.yosupo.jp/problem/enumerate_primes

Counting Primes

https://judge.yosupo.jp/problem/counting_primes

Totient Function

https://judge.yosupo.jp/problem/sum_of_totient_function

Copy
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;

(project euler)

(topcoder problem)

Problems

Here are some practice problems for everyone to understand the methods mentioned above. Such problems are relatively few, so if you have other sources of problems, please feel free to share.