Du's Second Division Sieve

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|\in \mathcal{O}(\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}\\ & \in \mathcal{O}(\sqrt{n})\end{array}$$

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

Du’s Second Division Sieve is an algorithm that computes $S_f(1),S_f(2),\dots ,S_f(\lfloor n^{\frac{2}{3}}\rfloor -1)$ and $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$, if $S_g(1),S_g(2),\dots ,S_g(\lfloor n^{\frac{2}{3}}\rfloor -1)$, $S_g(\lfloor \frac{n}{1}\rfloor ),S_g(\lfloor \frac{n}{2}\rfloor ),\dots ,S_g(\lfloor \frac{n}{n}\rfloor )$, $S_{f\ast g}(1),S_{f\ast g}(2),\dots ,S_{f\ast g}(\lfloor n^{\frac{2}{3}}\rfloor -1)$, 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, in $\mathcal{O}(n^{\frac{2}{3}})$ time and $\mathcal{O}(n^{\frac{2}{3}})$ 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 -1\}\wedge \exists p\in \mathbb{P},\exists e\in \mathbb{N},k=p^e\}$, find $f(k)$.

2. Use the results from Step 1 to find $f(1),f(2),\dots ,f(\lfloor n^{\frac{2}{3}}\rfloor -1)$.

3. Use the results from Step 2 to find $S_f(1),S_f(2),\dots ,S_f(\lfloor n^{\frac{2}{3}}\rfloor -1)$.

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 -1\}$, apply the lemma to find $S_f(k)$.

std::unordered_map<int, int> du(int n, const std::unordered_map<int, int> &sg, const std::unordered_map<int, int> &sh) {
	int m = std::pow(n, .67);
 
	std::vector<int> f(m);
	f[1] = 1;
	for (int i = 2; i < m; i++) {
		if (pk[i] == i) {
			f[i] = sh.at(i) - sh.at(i - 1);
			for (int j = i / pf[i]; j; j /= pf[i]) {
				f[i] -= f[j] * (sg.at(i / j) - sg.at(i / j - 1));
			}
		} else {
			f[i] = f[i / pk[i]] * f[pk[i]];
		}
	}
 
	std::unordered_map<int, int> sf;
	sf[1] = f[1];
	for (int i = 1; i < m; i++) {
		sf[i] = sf[i - 1] + f[i];
	}
	for (int i = n / m; i > 0; i--) {
		sf[n / i] = sh.at(n / i);
		for (int j = 2; j <= n / i; j = n / i / (n / i / j) + 1) {
			sf[n / i] -= (sg.at(n / i / (n / i / j)) - sg.at(j - 1)) * sf[n / i / j];
		}
	}
	return sf;
}

Proof

Applying the lemma yields that this algorithm solves the problem in

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

time.

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