Prefix Sums of Multiplicative Functions

Initial Overview

Definition

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

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

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

Examples

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.

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.

Dirichlet Convolution

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.

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 we have

Möbius Inversion

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 \cdot \mu = e$， $g \cdot \mu = f \cdot I \cdot \mu = f \cdot 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}$

Example - Sum of Divisors

Explanation

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.

Implementation

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

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

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 $\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.

Implementation

Time Complexity: $\mathcal{O}(n^{3/4})$

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;

Example - Enumerate Primes

Explanation

Remember the old $\mathcal{O}(N \log N)$ Eratosthenes' sieve here?

To solve this problem, we have to improve the complexity of the sieve to $\mathcal{O}(N)$. Check out this CF blog entry for further information.

Copy
std::vector<int> prime;
bool is_composite[MAX_N];

void sieve(int n) {
	std::fill(is_composite, is_composite + n, false);
	for (int i = 2; i < n; ++i) {
		if (!is_composite[i]) { prime.push_back(i); }
		for (int j = 2; i * j < n; ++j) { is_composite[i * j] = true; }
	}
}

This problem requires finding the count of prime numbers not exceeding $N$ and then calculating the sum of primes based on specific conditions.

1. We first run our sieve to get all the prime numbers not exceeding $N$.
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.

Implementation

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

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 500000000;

using ll = long long;

 Code Snippet: Sieve Implementation (Click to expand)

int main() {

Example - Counting Primes

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(N^{3/4}\log^{1/2}N)$.

Implementation

Time Complexity: $\mathcal{O}(n^{3/4})$

Copy
#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 a faster way to compute primes in O(n^2/3), see Maksim1744’s Codeforces Blog for more details. Below is the implementation using the fenwick code snippet from the PURS module

Implementation

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

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