Du's First Division Sieve

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$) in $\mathcal{O}(n^{\frac{3}{4}})$ time and $\mathcal{O}(\sqrt{n})$ space, 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.

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 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> sf;
for (int i : s) {
	sf[i] = sh[i];
	for (int j = 2; j <= i; j = i / (i / j) + 1) {
		sf[i] -= (sg[i / (i / j)] - sg[j - 1]) * sf[i / j];
	}
	sf[i] /= sg[1];
}
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(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)$$ $$\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)$$

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