Du's Second Multiplication Sieve

Let $S_f(n)={\sum }_{k=1}^{n}f(k)$.

Du’s Second Multiplication Sieve is an algorithm that computes $S_{f\ast g}(\lfloor \frac{n}{1}\rfloor ),S_{f\ast g}(\lfloor \frac{n}{2}\rfloor ),\dots ,S_{f\ast g}(\lfloor \frac{n}{n}\rfloor )$ for multiplicative functions $f$ and $g$ in $\mathcal{O}(n^{\frac{2}{3}})$ time and $\mathcal{O}(n^{\frac{2}{3}})$ space, if $f(1),f(2),\dots ,f(\lfloor n^{\frac{2}{3}}\rfloor )$, $S_f(\lfloor \frac{n}{1}\rfloor ),S_f(\lfloor \frac{n}{2}\rfloor ),\dots ,S_f(\lfloor \frac{n}{n}\rfloor )$, $g(1),g(2),\dots ,g(\lfloor n^{\frac{2}{3}}\rfloor )$, and $S_g(\lfloor \frac{n}{1}\rfloor ),S_g(\lfloor \frac{n}{2}\rfloor ),\dots ,S_g(\lfloor \frac{n}{n}\rfloor )$ are given.

Hint

This problem can also be solved by Du’s First Multiplication Sieve in $\mathcal{O}(n^{\frac{3}{4}})$ time and $\mathcal{O}(\sqrt{n})$ space.

Algorithm

Lemma

$$\forall n\in {\mathbb{Z}}_{+},S_{f\ast g}(n)=\sum _{d=1}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)$$

Proof

$$\begin{array}{rl}{S}_{f\ast g}(n)& =\sum _{k=1}^n(f\ast g)(k)\\ & =\sum _{k=1}^n\sum _{d\mid k}f\left(\frac{k}{d}\right)g(d)\\ & =\sum _{d=1}^{n}g(d)\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }f(k)\\ & =\sum _{d=1}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)\end{array}$$

1. For each $k$ in $\{k:k\in \{1,2,\dots ,\lfloor n^{\frac{2}{3}}\rfloor \}\wedge \exists p\in \mathbb{P},\exists e\in \mathbb{N},k=p^e\}$, find $(f\ast g)(k)$.

2. Find $(f\ast g)(1),(f\ast g)(2),\dots ,(f\ast g)(\lfloor n^{\frac{2}{3}}\rfloor )$ using the results from Step 1.

3. Find $S_{f\ast g}(1),S_{f\ast g}(2),\dots ,S_{f\ast g}(\lfloor n^{\frac{2}{3}}\rfloor )$ using the results from Step 2.

4. For each $k$ in $\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}\setminus \{1,2,\dots ,\lfloor n^{\frac{2}{3}}\rfloor \}$, applying the lemma to find $S_{f\ast g}(k)$.

This algorithm solves the problem in $\mathcal{O}(n^{\frac{2}{3}})$ time and $\mathcal{O}(n^{\frac{2}{3}})$ space.

std::vector<int> h(n23 + 1);
h[1] = 1;
for (int i = 2; i <= n23; i++) {
	if (pk[i] == i) {
		h[i] = 0;
		for (int j = i; j; j /= pf[i]) {
			h[i] += f[j] * g[i / j];
		}
	} else {
		h[i] = f[i / pk[i]] * g[pk[i]];
	}
}
 
std::unordered_map<int, int> sh;
for (int i = 1; i <= n23; i++) {
	sh[i] = sh[i - 1] + h[i];
}
for (int i = n / n23; i > 0; i--) {
	sh[n / i] = 0;
	for (int j = 1; j <= n / i; j = n / i / (n / i / j) + 1) {
		sh[n / i] += (sg[n / i / (n / i / j)] - sg[j - 1]) * sf[n / i / j];
	}
}
return sh;

Proof

Lemma

$$\forall n\in {\mathbb{Z}}_{+},\left|\left\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \right\}\right|\le 2\sqrt{n}$$

Proof

$$\begin{array}{rl}\left|\left\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \right\}\right|& \le \left|\left\{\lfloor \frac{n}{d}\rfloor :d\in \{1,2,\dots ,\lfloor \sqrt{n}\rfloor \}\right\}\right|+\left|\left\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \right\}\cap \{1,2,\dots ,\lfloor \sqrt{n}\rfloor \}\right|\\ & \le 2\sqrt{n}\end{array}$$

Applying the lemma yields that

$$T(n)\in \mathcal{O}\left(n^{\frac{2}{3}}+\sum _{d=1}^{\lfloor n^{\frac{1}{3}}\rfloor }\sqrt{\frac{n}{d}}\right)$$

Therefore, since

$$\begin{array}{rl}\mathcal{O}\left(\sum _{d=1}^{\lfloor n^{\frac{1}{3}}\rfloor }\sqrt{\frac{n}{d}}\right)& =\mathcal{O}\left(\sqrt{n}\sum _{d=1}^{\lfloor n^{\frac{1}{3}}\rfloor }{d}^{-\frac{1}{2}}\right)\\ & =\mathcal{O}\left(\sqrt{n}{\int }_0^{n^{\frac{1}{3}}}{x}^{-\frac{1}{2}}\mathrm{d}x\right)\\ & =\mathcal{O}(n^{\frac{2}{3}})\end{array}$$

it follows that

$$\mathcal{O}\left(n^{\frac{2}{3}}+\sum _{d=1}^{\lfloor n^{\frac{1}{3}}\rfloor }\sqrt{\frac{n}{d}}\right)=\mathcal{O}(n^{\frac{2}{3}})$$

Therefore,

$$T(n)\in \mathcal{O}(n^{\frac{2}{3}})$$