Zhou Sieve

Prerequisite knowledge

• Multiplicative functions

Definition

The Zhouge sieve is a sieve that computes the prefix sums of most multiplicative functions in sublinear time.

We use $\displaystyle\sum_{i=1}^nf(i)$ as an example to explain its principle.

Conventions

• $\mathbb P$ denotes the set of primes, and $p_i$ denotes the $i$-th prime.
• $m$ denotes the number of primes not exceeding $\sqrt n$.

Requirement

For $p\in\mathbb P,c\in\mathbb N$, $f(p^c)$ must be a low-degree polynomial in $p$.

Idea

• Any integer in $[1,n]$ has at most one $>\sqrt n$ prime factor.
• The values $\left\lfloor\dfrac ni\right\rfloor(i\in[1,n]\cap\mathbb N)$ take only about $\sqrt n$ distinct values, which can be used to reduce the time complexity.

Process

Partition all integers in $[1,n]$ according to whether they have a $>\sqrt n$ prime factor:

$$\sum_{i=1}^nf(i)=\sum_{i=1}^n\left[\exists d\in(\sqrt n,n]\cap\mathbb P,d\mid i\right]f(i)+\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i)$$

For the first part, enumerate the largest factor and use the multiplicativity of the function to obtain

$$\sum_{i=1}^nf(i)=\sum_{i=1}^{\sqrt n}f(i)\cdot\left(\sum_{d=\lfloor\sqrt n\rfloor+1}^{\lfloor\frac ni\rfloor}[d\in\mathbb P]f(d)\right)+\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i)$$

The two parts can be computed separately.

Part 1

Compute $\displaystyle\sum_{i=1}^{\sqrt n}f(i)\cdot\left(\sum_{d=\lfloor\sqrt n\rfloor+1}^{\lfloor\frac ni\rfloor}[d\in\mathbb P]f(d)\right)$.

Enumerate $i$, then compute the expression in parentheses in $O(1)$ time.

Let $\displaystyle g(t,l)=\sum_{i=1}^l[\forall j\in[1,t],\gcd(i,p_j)=1]f(i)$, namely, the sum over the numbers in $[1,l]$ that are coprime to all of $p_1,p_2,\dots,p_t$ of their $f$ values.

The computation in Part 1 becomes $\displaystyle\sum_{i=1}^{\sqrt n}f(i)\cdot g\left(m,\left\lfloor\frac ni\right\rfloor\right)$.

The base case is $g(0,l)=\sum_{i=1}^lf(i)$, and the transition is $g(t,l)=g(t-1,l)-f(p_t)\cdot g\left(t-1,\left\lfloor\frac l{p_t}\right\rfloor\right)$.

The variable $l$ has about $\sqrt n$ possible values, and each requires enumerating its prime factors, giving complexity $\displaystyle O\left(\frac{\sqrt n}{\ln\sqrt n}\cdot\sqrt n\right)= O\left(\frac n{\log n}\right)$. This needs to be optimized.

Observe that when $p_{t+1}^2>l$, the only number satisfying the condition is $1$, so $g(t,l)=f(1)=1$.

When $p_t^2>l$, substituting this into the recurrence gives $g(t,l)=g(t-1,l)-f(p_t)$.

Therefore, once $p_t^2>l$ is found, stop the transition and call this $t$ value $t_l$. Then $\forall t>t_l,g(t,l)=g(t_l,l)-\sum_{i=t_l}^{t-1}f(p_i)$.

By preprocessing the prefix sums of $f$ over the primes, $g$ can be obtained quickly, reducing the time complexity to $O\left(\dfrac{n^{\frac34}}{\log n}\right)$.

Part 2

Compute $\displaystyle\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i)$.

Let $\displaystyle h(t,l)=\sum_{i=1}^l\left[i=\prod_{j=t}^mp_j^{c_j},c_j\in\mathbb N\right]f(i)$, namely, the sum over all numbers in $[1,l]$ whose prime factors are restricted to $p_t,p_{t+1},\dots,p_m$ of their $f$ values.

Part 2 asks for $h(0,n)$.

The base case is $h(m+1,l)=1$, and the transition is $\displaystyle h(t,l)=h(t+1,l)+\sum_{c\in\mathbb N^*}f(p_t^c)\cdot h\left(t+1,\left\lfloor\frac l{p_t^c}\right\rfloor\right)$.

The variable $l$ has about $\sqrt n$ possible values, so the direct transition takes $\displaystyle O\left(\sqrt n\cdot\frac{\sqrt n}{\ln\sqrt n}\right)= O\left(\frac n{\log n}\right)$ time. This needs to be optimized.

As with the optimization for $g$, when $p_t>l$, the only number that can be formed from $p_t,p_{t+1},\dots,p_m$ is $1$, so $h(t,l)=f(1)=1$.

Similarly, $\forall p_t^2>l,h(t,l)=h(t+1,l)+f(p_t)$.

Therefore, once $p_t^2>l$ is found, stop the transition and call this $t$ value $t_l$. Whenever $h$ is subsequently used, add the current $h$ value plus $\displaystyle\sum_{i=p_{t_l}}^{\min(l,\sqrt n)}[i\in\mathbb P]f(i)$, as needed.

The time complexity is reduced to $O\left(\dfrac{n^{\frac34}}{\log n}\right)$.

Summation

The sum of the answers to Part 1 and Part 2 is $\displaystyle\sum_{i=1}^nf(i)$.

References

Notes on linear sieves, the Du sieve, and the Zhouge sieve for multiplicative functions