In this module we introduce how to compute prefix sums of certain number-theoretic functions in sublinear time. Here are some examples:

This module (part 1) will focus on topics relating to the first two focus problems. Prime counting and related applications will be deferred to part 2.

Multiplicative Functions

The functions that we'd like to compute prefix sums over in the first two focus problems are both multiplicative.

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

Resources

As this module is supposed to serve as a gentle introduction to this topic, we will usually describe only the simplest solution that passes the given constraints. Solutions with asymptotically better time complexities can be found in blogs such as the following, though keep in mind that they might not be much faster under the given constraints.

Warm-Up

Let's start with introducing a set of numbers $Q_N$ we often work with when computing prefix sums of multiplicative functions up to $N$.

Exercise for the reader: How large can this set be?

An important property of this set is that if $x\in Q_N$ then $Q_x \subseteq Q_N$.

Implementation

Example - Sum of Divisors

Hint: The time complexity is the same as for the previous problem.

Solution

Implementation

Dirichlet Convolution

Introduction

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 function $f$ and the identity function $I$. For example, if $n = \prod_{i=1}^{t} p_i^{k_i}$ and $g=f* I$, then $g(n) = \sum_{d|n} f(d)$. If $f$ is multiplicative, then we have

If we wish to recover $f$ from $g$, we can write $g* \mu = (f* I)* \mu=f* (I* \mu)=f* e=f$. That is, $f(n) = \sum_{d|n} g(d) \cdot \mu\left(\frac{n}{d}\right)$. This is known as Möbius inversion.

Example - Dirichlet Convolution and Prefix Sums

Given $\{f_x | x \in Q_N\}$ and $\{g_x | x \in Q_N\}$, then if we define $h=f*g$, we can compute $\{h_x | x \in Q_N\}$ in sublinear time.

Solution

Implementation

Example - Dirichlet Inverse and Prefix Sums

Suppose instead of finding $h=f*g$ given $f$ and $g$, we'd like to recover $g$ given $h$ and $f$.

Solution

Implementation

Example - Totient Sum

Solution

Implementation

Problems

The first two problems are from the first resource.