# Calculating $\sum \sigma (n)$

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}$.

• @user1952009 I edited my post. I think that for values $m \ge n/k$, then the sum for $k \le \sqrt{n}$ can be calculated manually. – qwr Jul 2 '17 at 0:42

## 2 Answers

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}$

• I noticed it before but forgot about it... The idea is that for $\sqrt{n} < m \le n$, $m$ must be counted once? – qwr Jul 1 '17 at 16:53
• I'm still not sure I understand. Take $n=10$. Only for $k > 5$ are the divisors counted once. 4 and 5 are both counted twice. – qwr Jul 2 '17 at 0:14
• @qwr voila ${}{}{}$ – reuns Jul 2 '17 at 1:11
• The old formula was easier to understand... I think I get the general idea, I'll try my own equation – qwr Jul 2 '17 at 1:27
• @qwr It wasn't correct. You have only one thing to prove : the sentence in bold. – reuns Jul 2 '17 at 1:31

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

• yes it works too. – reuns Jul 2 '17 at 2:38
• @user1952009 the formula was actually wrong for some values. It is corrected now. – qwr Jul 2 '17 at 3:06