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 https://judge.yosupo.jp/problem/enumerate_primes

Let the prime numbers be $p_0 < p_1 < p_2 < \cdots$ (i.e. $p_0 = 2, p_1 = 3, p_2 = 5,$ and so on).

You are given integers $N, A,$ and $B$. Find $\pi(N)$ (the number of primes no greater than $N$), and print $\sum_{i} p_{Ai+B}$ for nonnegative integers $i$ with $\sum_{i} p_{Ai+B} \leq N$.

Constraints

• $1 \leq N \leq 5 \times 10^8$
• $0 \leq A < B \leq N$
• $0 \leq B < A \leq N$
• $0 \leq X \leq 10^6$ where $X = \# \{ i \in \mathbb{Z}_{\geq 0} \mid \sum_{i} p_{Ai+B} \leq N \}$

Approach:

First a review on linear sieve, this will be used in both focus problem 1 and 3:

Copy
void get_prime(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) primes[++cnt] = i;
		for (int j = 1; primes[j] <= n / i; j++) {
			st[i * primes[j]] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

Focus problem 1 requires finding the count of prime numbers not exceeding a given integer N and then calculating the sum of primes based on specific conditions. The provided solution employs the Sieve of Eratosthenes algorithm, which efficiently finds prime numbers up to a given limit. Here's how the solution works:

1. Sieve of Eratosthenes: The algorithm efficiently identifies prime numbers up to a given limit by marking multiples of primes as composite.
2. Input and Initialization: The program reads input values N, A, and B, and initializes arrays to store prime numbers (p) and their count (pc).
3. Counting and Summing Primes: After sieving for prime numbers up to N, the program calculates the count of terms (x) in the sum $\sum_{i} p_{Ai+B}$ that do not exceed N. It does this by considering the quotient of the total count of prime numbers divided by A, adjusting for the remainder.
4. Output: The program prints the count of prime numbers (pc) and the count of terms in the sum (x). Then, it outputs the prime numbers contributing to the sum, starting from index B and skipping A elements each time.

Copy
#include <bits/stdc++.h>
using namespace std;
constexpr int N(5e8), M(3.2e7);
int p[M], pc;
void sieve(int n) {
	if (n < 2) return;
	vector<bool> np(n + 1);
	p[pc++] = 2;
	int i;
	for (i = 3; 1ll * i * i <= n; i += 2) {

Focus problem # 2

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.

Copy
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

long long n, i, a, b;
long long sum;

int main() {
	scanf("%lld", &n);

Focus problem # 3

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.

Copy
#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int primes[N];
ll phi[N];
bool st[N];
int cnt;

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.