Du's Second Division Sieve

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

Du’s Second Division Sieve is an algorithm that computes $S_f(\lfloor \frac{n}{1}\rfloor ),S_f(\lfloor \frac{n}{2}\rfloor ),\dots ,S_f(\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 $g(1),g(2),\dots ,g(\lfloor n^{\frac{2}{3}}\rfloor )$, $S_g(\lfloor \frac{n}{1}\rfloor ),S_g(\lfloor \frac{n}{2}\rfloor ),\dots ,S_g(\lfloor \frac{n}{n}\rfloor )$, $(f\ast g)(1),(f\ast g)(2),\dots ,(f\ast g)(\lfloor n^{\frac{2}{3}}\rfloor )$, and $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 )$ are given.

Hint

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

Algorithm

Lemma

$$\forall n\in {\mathbb{Z}}_{+},S_f(n)=S_{f\ast g}(n)-\sum _{d=2}^{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)\\ & =S_f(n)+\sum _{d=2}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)\end{array}$$ $$S_{f\ast g}(n)=S_f(n)+\sum _{d=2}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)⟺S_f(n)=S_{f\ast g}(n)-\sum _{d=2}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)$$

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(k)$.

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

3. Find $S_f(1),S_f(2),\dots ,S_f(\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(k)$.

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

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}})$$