Du's First 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 First 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 arithmetic functions $f$ and $g$ ($g(1)\ne 0$), if $S_g(\lfloor \frac{n}{1}\rfloor ),S_g(\lfloor \frac{n}{2}\rfloor ),\dots ,S_g(\lfloor \frac{n}{n}\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, in $\mathcal{O}(n^{\frac{3}{4}})$ time and $\mathcal{O}(\sqrt{n})$ space.

Algorithm

Lemma

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

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

Applying the lemma to find $S_f$ yields an algorithm that solves in the problem in $\mathcal{O}(n^{\frac{3}{4}})$ time and $\mathcal{O}(\sqrt{n})$ space.

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::sqrt(n);
 
	std::vector<int> d;
	for (int i = 1; i < m; i++) {
		if (n / (n / i) == i) {
			d.push_back(i);
		}
	}
	for (int i = n / m; i > 0; i--) {
		d.push_back(n / i);
	}
	d.erase(std::unique(d.begin(), d.end()), d.end());
 
	std::unordered_map<int, int> sf;
	for (int i : d) {
		sf[i] = sh.at(i);
		for (int j = 2; j <= i; j = i / (i / j) + 1) {
			sf[i] -= (sg.at(i / (i / j)) - sg.at(j - 1)) * sf[i / j];
		}
		sf[i] /= sg.at(1);
	}
	return sf;
}

Proof

Applying the lemma yields that this algorithm solves the problem in

$$\mathcal{O}\left(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)$$

time.

$$\mathcal{O}\left(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)\subseteq \mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{k}+\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{\frac{n}{k}}\right)$$

Since

$$\begin{array}{rl}\mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{k}\right)& \subseteq \mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }{n}^{\frac{1}{4}}\right)\\ & =\mathcal{O}(n^{\frac{3}{4}})\end{array}$$

and

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

it follows that

$$\mathcal{O}\left(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)\subseteq \mathcal{O}(n^{\frac{3}{4}})$$

Therefore,

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