What is the most efficient way to compute sum of sum of divisors of all numbers from 1 to n?

Question

​​$σ_1(i)$ be the sum of divisors of $i$,

Calculate

​$S(n) = \sum_{i=1}^n σ_1(i)$

I am looking for something better than $O(\sqrt{n})$

To address @ingix's question here is my $O(\sqrt{n})$ python code: The beauty of this approach is you dont need to know $σ_1(i)$ for each i, you just need to have all their ingredients in the final sum.

# http://oeis.org/A024916

def triangular(n):
    return n * (n + 1) // 2

def A024916(n):
    sum = 0
    up = 0
    i = 1
    while i * i < n:
        now = n // i
        before = n // (i + 1)
        # trick = http://oeis.org/A257212
        sum += i * (triangular(now) - triangular(before))
        up = before
        i += 1
    for i in range(1, up + 1):
        sum += n // i * i
    return sum


n = int(input())
if n <= 2:
    print([1, 4][n - 1])
else:
    print(A024916(n))

EDIT: I found a paper which does it in $O(n^{1/3})$ . Will update once I understand it properly.

Mean while if someone has a better or similar approach you are welcome.

Answer 1

By Dirichlet's hyperbola method, we have \begin{aligned} \sum_{k\le n}\sigma(k) &=\sum_{mt\le n}t=\sum_{m\le\sqrt n}\sum_{t\le n/m}t+\sum_{t\le\sqrt n}t\sum_{m\le n/t}1-\sum_{m\le\sqrt n}\sum_{t\le\sqrt n}t \\ &=\sum_{m\le\sqrt n}\frac12\left\lfloor\frac nm\right\rfloor\left(1+\left\lfloor\frac nm\right\rfloor\right)+\sum_{t\le\sqrt n}t\left\lfloor\frac nt\right\rfloor-\frac12\lfloor\sqrt n\rfloor^2(1+\lfloor\sqrt n\rfloor). \end{aligned}

Combining all terms, we get $$ \sum_{k\le n}\sigma(k)=\sum_{m\le\sqrt n}\frac12\left\lfloor\frac nm\right\rfloor\left(2m+1+\left\lfloor\frac nm\right\rfloor\right)-\frac12\lfloor\sqrt n\rfloor^2(1+\lfloor\sqrt n\rfloor), $$ and from the sigma notation we see that this can also be used to create an $O(\sqrt n)$ algorithm.