Let $d(n)$ is the number of divisors of $n$. Example: $d(6) = 4$ because $6$ has $4$ divisors {$1, 2, 3, 6$} (Sequence A000005).
Let $D(n)$ is the sum of first $n$ functions $d(x)$. Or we have $D(n) = \overset{n}{\underset{x=1}{\Large \Sigma}} d(x)$ (Sequence A006218).
It is known that $D(n) = \overset{n}{\underset{x=1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \normalsize = 2\overset{\lfloor \sqrt{n} \rfloor}{\underset{x=1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \normalsize - {\lfloor \sqrt{n} \rfloor}^2$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ [1]
It is also known that $S = \Large\{ \Large \lfloor \normalsize \frac{n}{1} \Large \rfloor \normalsize, \Large \lfloor \normalsize \frac{n}{2} \Large \rfloor \normalsize, \dots, \Large \lfloor \normalsize \frac{n}{n - 1} \Large \rfloor \normalsize, \Large \lfloor \normalsize \frac{n}{n} \Large \rfloor \normalsize \Large \Large \}$ have $O(\sqrt{n})$ unique numbers or/and $|S| \leq 2\sqrt{n} + 1$ $\ \ \ \ \ \ \ \ \ \ \ $ [2]
Using [1] or [2] the function $D(n)$ can be calculated in $O(\sqrt{n})$.
Furthurmore, we can also calculate $D(n)$ in $O(\sqrt[3]{n})$ using the algorithm Richard Sladkey described in the paper A Successive Approximation Algorithm for Computing the Divisor Summatory Function $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ [3]
Let $s(n)$ is the sum of divisors of $n$. Example: $d(6) = 4$ because $6$ has $4$ divisors {$1, 2, 3, 6$} (Sequence A000203).
Let $S(n)$ is the sum of first $n$ functions $s(x)$. Or we have $S(n) = \overset{n}{\underset{x=1}{\Large \Sigma}} d(x)$ (Sequence A024916).
It is known that $S(n) = \overset{n}{\underset{x=1}{\Large \Sigma}} \overset{\Large \lfloor \normalsize \frac{n}{x} \Large \rfloor}{\underset{k=1}{\Large \Sigma}} k = \overset{n}{\underset{x=1}{\Large \Sigma}} \Large ( \normalsize x \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \Large ) \normalsize$
My question-1: Is there a simple $O(\sqrt{n})$ sigma formula other than using the lemma [2]
My question-2: But can it be calculated in $O(\sqrt[3]{n})$. Since this table calculated for $n = 10^{36}$
Let $T(n) = \overset{n}{\underset{x=1}{\Large \Sigma}} \Large ( \normalsize d(x) \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor \Large ) \normalsize$ (Sequence A061201).
My question-3: Is there a simple $O(\sqrt{n})$ sigma formula or how can I use the lemma [2] to calculate in $O(\sqrt{n})$
My question-4: Can it be calculated faster than $O(\sqrt{n})$. Since this table calculated for $n = 10^{23}$