2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – qwr Jul 2 '17 at 0:42
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I noticed it before but forgot about it... The idea is that for $\sqrt{n} < m \le n$, $m$ must be counted once? $\endgroup$ – qwr Jul 1 '17 at 16:53
  • $\begingroup$ 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. $\endgroup$ – qwr Jul 2 '17 at 0:14
  • $\begingroup$ @qwr voila ${}{}{}$ $\endgroup$ – reuns Jul 2 '17 at 1:11
  • $\begingroup$ The old formula was easier to understand... I think I get the general idea, I'll try my own equation $\endgroup$ – qwr Jul 2 '17 at 1:27
  • $\begingroup$ @qwr It wasn't correct. You have only one thing to prove : the sentence in bold. $\endgroup$ – reuns Jul 2 '17 at 1:31
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ yes it works too. $\endgroup$ – reuns Jul 2 '17 at 2:38
  • $\begingroup$ @user1952009 the formula was actually wrong for some values. It is corrected now. $\endgroup$ – qwr Jul 2 '17 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.