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

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

3. Use the results from Step 2 to find $S_{f\ast g}(1),S_{f\ast g}(2),\dots ,S_{f\ast g}(\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\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::unordered_map<int, int> du(int n, const std::unordered_map<int, int> &sf, const std::unordered_map<int, int> &sg) {
	int m = std::pow(n, .67);
 
	std::vector<int> h(m);
	h[1] = 1;
	for (int i = 2; i < m; i++) {
		if (pk[i] == i) {
			h[i] = 0;
			for (int j = i; j; j /= pf[i]) {
				h[i] += (sf.at(j) - (j > 1 ? sf.at(j - 1) : 0)) * (sg.at(i / j) - (i > j ? sg.at(i / j - 1) : 0));
			}
		} else {
			h[i] = h[i / pk[i]] * h[pk[i]];
		}
	}
 
	std::unordered_map<int, int> sh;
	sh[1] = h[1];
	for (int i = 2; i < m; i++) {
		sh[i] = sh[i - 1] + h[i];
	}
	for (int i = n / m; 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.at(n / i / (n / i / j)) - (j > 1 ? sg.at(j - 1) : 0)) * sf.at(n / i / j);
		}
	}
	return sh;
}

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