Calculating $\sum \sigma (n)$

Question

From $$\sum_{k=1}^n{\sigma(k)} = \sum_{k=1}^n k \left\lfloor \frac{n}{k} \right\rfloor$$ the observation is for large ranges of $k$, $\lfloor n/k \rfloor$ is constant. So the sum is equal to $$\left (\sum_{n/2 < k \le n}k\ \right ) + 2 \left (\sum_{n/3 < k \le n/2}k\ \right ) + \cdots$$

Calculating the sum of $k$ over a range is easy, so the difficult part is determining the range for each sum. That is, determining which ranges for large $k$ is $n/(m+1) < k \le n /m$ nonempty. OEIS A024916 lists a program by P. L. Patodia that is definitely sublinear, but I'm not sure what the program is calculating. From what I can tell it is calculating $k$ for $m$ up to $\sqrt{n}$ and then somehow using modulus to calculate the rest. So I am looking for an explanation or resources that explain how to calculate this sum in sublinear time.

Edit: I think Codeforces solution 616E could be relevant. The solution splits the sum into two cases, with either $k \le \sqrt{n}$ or $\left\lfloor \frac{n}{k} \right\rfloor \le \sqrt{n}$.

Answer 1

Splitting the sum into two cases, $k \le \sqrt{n}$ and $\left \lfloor \frac{n}{k} \right\rfloor \le \sqrt{n}$, considering the possible overlap:

$$\sum_{k=1}^{n}{k \left\lfloor \frac{n}{k} \right\rfloor} = \sum_{m=1}^{\lfloor \sqrt{n} \rfloor}{m \left( \sum_{k=\left\lfloor \frac{n}{m+1} \right\rfloor +1 }^{\left\lfloor \frac{n}{m} \right\rfloor}{k} \right)} + \sum_{k=1}^{k_{max}}{k \left\lfloor \frac{n}{k} \right\rfloor}$$

$$k_{max} = \begin{cases} \lfloor \sqrt{n} \rfloor, & \text{if} \ \lfloor \sqrt{n} \rfloor \neq \left \lfloor \frac{n}{\lfloor \sqrt{n} \rfloor} \right\rfloor \\ \lfloor \sqrt{n} \rfloor - 1, & \text{otherwise} \end{cases}$$

Using the $O(1)$ formula for sum of an arithmetic sequence, here is Python code for $O(\sqrt{n})$ aglorithm:

def SIGMA1(n):
    isqrt = int(n**0.5)
    s = 0
    for m in range(1, isqrt+1):
        a = n // (m+1) + 1
        b = n // m
        s += m * (a+b) * (1-a+b) // 2

    for k in range(1, isqrt):
        s += k * (n // k)

    if isqrt != n//isqrt:
        s += isqrt * (n//isqrt)

    return s

Answer 2

There is a working matlab code for the $\mathcal{O}(\sqrt{n})$ algorithm :

    function [r1,r2] = sum_divisors(n)
      %reference version O(n)
      r1 = sum( (1:n) .* floor(n./(1:n)));


      %second version O(sqrt(n))
      r2 = n*(n+1)/2;
      N = floor(sqrt(n));
      for k= 1:N-1
          r2 = r2 + k*(k+1)/2 * ( floor(n./k)-floor(n./(k+1)));
      end

      for m= 2:floor(n/N)
          k = floor(n/m);
          r2 = r2 + k*(k+1)/2 ;

      end

The idea is that summing by parts $$\sum_{k=1}^n k \lfloor \frac{n}{k} \rfloor = (\sum_{k=1}^n k) + \sum_{k=1}^{n-1} (\sum_{l=1}^k l) (\lfloor \frac{n}{k} \rfloor-\lfloor \frac{n}{k+1} \rfloor)$$

$$ = \frac{n(n+1)}{2}+\sum_{k=1}^{\lfloor \sqrt{n} \rfloor-1} \frac{k(k+1)}{2}(\lfloor \frac{n}{k} \rfloor-\lfloor \frac{n}{k+1} \rfloor) + \sum_{ m=2}^{n/\lfloor \sqrt{n} \rfloor} \frac{\lfloor \frac{n}{m} \rfloor(\lfloor \frac{n}{m} \rfloor+1)}{2}$$ where we have splitted the $\sum_{k=1}^n$ at $\sqrt{n}$ because for $k \ge \sqrt{n} $ : $\lfloor \frac{n}{k} \rfloor-\lfloor \frac{n}{k+1} \rfloor \ne 0$ iff $\lfloor \frac{n}{k} \rfloor-\lfloor \frac{n}{k+1} \rfloor = 1$ iff $k = \lfloor \frac{n}{m} \rfloor, m = \lfloor \frac{n}{k} \rfloor$ for some $m \le \sqrt{n}$

Answer 3

Based on the fact that there are $O(\sqrt[3]{n})$ different slope. You can calculate $\overset{n}{\underset{x = 1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{x} \Large \rfloor$ in $O(\sqrt[3]{n})$ like how this paper describe. I think it is also possible to apply it into your problem