Sums of sum of divisors in sublinear time

Question

Given a number \$n\$, we have its sum of divisors, \$\sigma(n)\ = \sum_{d | n} {d}\$, that is, the sum of all numbers which divide \$n\$ (including \$1\$ and \$n\$). For example, \$\sigma(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56\$. This is OEIS A000203.

We can now define the sum of sum of divisors as \$S(n) = \sum_{i=1}^{n}{\sigma(i)}\$, the sum of \$\sigma(i)\$ for all numbers from \$1\$ to \$n\$. This is OEIS A024916.

Your task is to calculate \$S(n)\$, in time sublinear in \$n\$, \$o(n)\$.

Test cases

10 -> 87
100 -> 8299
123 -> 12460
625 -> 321560
1000 -> 823081
1000000 (10^6) -> 822468118437
1000000000 (10^9) -> 822467034112360628

Rules

• Your complexity must be \$o(n)\$. That is, if your code takes time \$T(n)\$ for input \$n\$, you must have \$\lim_{n\to\infty}\frac{T(n)}n = 0\$. Examples of valid time complexities are \$O(\frac n{\log(n)})\$, \$O(\sqrt n)\$, \$O(n^\frac57 \log^4(n))\$, etc.
• You can use any reasonable I/O format.
• Note that due to the limited complexity you can't take the input in unary nor output in it (because then the I/O takes \$\Omega(n)\$ time), and the challenge might be impossible in some languages.
• Your algorithm should in theory be correct for all inputs, but it's fine if it fails for some of the big test cases (due to overflow or floating-point inaccuracies, for example).
• Standard loopholes are disallowed.

This is code golf, so the shortest answer in each language wins.

Answer 1

Ruby, 55 52 bytes

Formula is adapted from this math.SE question. Runs in \$\mathcal{O}(\sqrt{n})\$.

-3 bytes thanks to @dingledooper.

->x{(1..$.=x**0.5).sum{(v=x/_1)*_1-(v*~v-$.*~$.)/2}}

Attempt This Online!

Answer 2

Python 2, 58 bytes

Runs in \$ \mathcal{O}(\sqrt{n}) \$ time.

f=lambda n,i=1:~i*i*(n/-~i-n/i)/2+(i<n and f(n,n/(n/-~i)))

Try it online!

Explanation

Note: @Neil's answer seems to use a similar approach to mine.

We first take the \$ O(n) \$-time formula \$ \sum_{i=1}^n{i \cdot \lfloor\frac{n}{i}\rfloor} \$, noticing that there can only be \$ O(\sqrt{n}) \$ unique values of \$ \lfloor\frac{n}{i}\rfloor \$. For example, if \$ n = 50 \$, the possible values of \$ i \$ for each \$ \lfloor\frac{n}{i}\rfloor \$ are:

 n//i |   i
------+-------
   1  | 26-50
   2  | 17-25
   3  | 13-16
   4  | 11-12
   5  | 9-10
   6  | 8-8
   7  | 7-7
   8  | 6-6
  10  | 5-5
  12  | 4-4
  16  | 3-3
  25  | 2-2
  50  | 1-1

Let \$ a \$ be a sorted list of all unique values of \$ \lfloor\frac{n}{i}\rfloor \$. For this example, \$ a = [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 16, 25, 50 ] \$. We can then construct a new summation that solves the problem in \$ O(\sqrt{n}) \$:

$$ \sum_{i=1}^{|a|}{\left\lfloor \frac{n}{a_{i}} \right\rfloor \times (T(a_{i}) - T(a_{i-1}))} $$

where \$ T(n) \$ is the sum of the first \$ n \$ positive integers, and assuming that \$ a_0 = 0 \$. Next, a bit of insight allows us to rearrange the summation like so:

$$ \sum_{i=1}^{|a|}{T(a_i) \times \left(\left\lfloor\frac{n}{a_i}\right\rfloor - \left\lfloor\frac{n}{a_i+1}\right\rfloor\right)} $$

To compute \$ a \$, we can apply the following recurrence:

$$ a_i = \left\lfloor\frac{n}{\lfloor n / (1+a_{i-1}) \rfloor}\right\rfloor $$

The proof is left as an exercise to the reader. Finally, we can compute \$ T(n) \$ using the formula \$ \frac{n(n+1)}{2} \$.

Answer 3

R, 52 bytes

\(x,y=1:x^.5,z=x%/%y)y%*%z+(z+1)%*%z/2-max(y)*sum(y)

Attempt This Online!

Golfed down version of Dominic's answer which in turn uses the same observation as ovs. Nothing crazy here; should run in \$\mathcal{O}\left(\sqrt n\right)\$ time, but saves bytes by using 1:sqrt(x) to truncate, and %*% to calculate the sumproduct.

Answer 4

Nibbles, 17 bytes (34 nibbles)

+:.;.,;^$-2/_$-;~$/*+$~$~$;$!$,_*

Attempt This Online!

Direct port of my R answer.

This feels very clunky, with half the tokens used for control-flow (,;,;;~) or explicit variable names ($_$$$$$;$$_); I suspect that one of the stack-based languages will be able to better this...

Bit-by-bit (in conjunction with the Nibbles quick reference and tutorial):
y (=floor(sqrt(x)): ^$-2
z (=floor(x/(1..y))), saving y: .,;^$-2/_$ (y saved as $)
triangle(z), saving z, y & triangle function: .;.,;^$-2/_$;~$/*+$~$~
triangle(z)-triangle(y): .;.,;^$-2/_$-;~$/*+$~$~$;$
(leaves z saved as $, y saved as @, x is _)

So now we can easily use the saved variables to calculate D: D = (1..y)*z + triangle(z)-triangle(y): +: .;.,;^$-2/_$-;~$/*+$~$~$;$ !$,_*

Answer 5

R, 61 51 49 bytes

Edit: saved 10 12 bytes by re-arrangement, goaded (and inspired) by Giuseppe golfing-down my original version in his answer

\(x,y=1:x^.5,z=x%/%y)min((2*y+z+1)%*%z-y^3-y^2)/2

Attempt This Online!

Golfed calculation based on the same Math.SE question used in ovs' Ruby answer.

Ungolfed

triangle=function(x)x*(x+1)/2
D=
function(x){
    y=sqrt(x)%/%1
    k=1:y
    sum(k*x%/%k+triangle(x%/%k))-triangle(y)*y
}

Answer 6

Scala 3, 75 bytes

Port of @ovs's Ruby answer in Scala.

---

x=>{val d=sqrt(x);(BigInt(1) to d).map(k=>x-x%k-(x/k* ~(x/k)-d* ~d)/2).sum}

Attempt This Online!

Answer 7

Charcoal, 41 38 bytes

 Ｎθ≔θη≔⁰ζＷη«≔÷θιε≔÷θ⊕εη≧⁺×⁻ιη÷×ε⊕ε²ζ»Ｉζ

Try it online! Link is to verbose version of code. Explanation: Uses the formula \$ A024916(n) = \sum_{i=1}^n i \lfloor n/i \rfloor \$ with the linked observation that it can be calculated more efficiently by grouping terms with the same value of \$ \lfloor n/i \rfloor \$, and then applying @dingledooper's rearrangement that \$ \sum_{j=1} \lfloor n/a_j \rfloor (T(a_j) - T(a_{j-1})) = \sum_{j=1} T(a_j) ( \lfloor n/a_j \rfloor - \lfloor n/a_{j+1} \rfloor ) \$ where \$ T(n) \$ are the triangular numbers to save 3 bytes.

 Ｎθ

Input \$ n \$.

≔θη

Start counting \$ \lfloor n / a_j \rfloor \$ down from \$ n \$.

≔⁰ζ

Start with no total.

Ｗη«

Repeat until \$ \lfloor n / a_j \rfloor \$ is zero. This also conveniently makes a copy of the value, so I can update the original variable in the loop while still being able to access its former value.

≔÷θιε

Calculate \$ a_j \$.

≔÷θ⊕εη

Calculate \$ \lfloor n / a_{j+1} \rfloor = \lfloor n / ( 1 + a_j ) \rfloor \$.

≧⁺×⁻ιη÷×ε⊕ε²ζ

Calculate \$ T(a_j) ( \lfloor n/a_j \rfloor - \lfloor n/a_{j+1} \rfloor ) \$, and accumulate it to the total.

»Ｉζ

Output the final total.

On TIO, \$ 10^{11} \$ takes about \$ 10 \$ times as long as \$ 10^9 \$, so the time complexity appears to be \$ O(\sqrt n) \$.

Answer 8

Python, 74 bytes

lambda n,i=0,k=1:(k>=i)*i*k+(i<k and f(n,j:=i+1,l:=n//j)+i*(l*~l-k*~k)//2)

Attempt This Online!

Old Python, 88 bytes

lambda n,k=0:sum(i*k*(k>i)+i*(k-~(j:=n//-~i))*(k-(k:=j))//2for i in range(int(n**.5)+1))

Attempt This Online!

Probably similar to @ovs's although found independently.

The basic idea is to regroup the given double sum by divisors and then count how many numbers in the range are a multiple of the divisor.

To achieve O(n^0.5) divisors with the same multiplicity are lumped together.

Answer 9

JavaScript (ES6), 54 bytes

Based on the formula found by ovs.

x=>(g=k=>++k*k>x?--k*k*~k/2:k*(q=x/k|0)-q*~q/2+g(k))``

Try it online!

---

JavaScript (ES11), 45 bytes

-3 bytes thanks to @tsh

A port of dingledooper's answer.

Expects a BigInt.

f=(n,q=n)=>q&&(i=n/q)*(q-n/++i)*i/2n+f(n,n/i)

Try it online!

Answer 10

K (ngn/k), 44 42 bytes

{+/-[q*k;x@s]+x@q:_y%k:1+!s:_%y}{-2!x*1+x}

-2 thanks to @coltim

Same formula as @ovs' answer.

Try it online!

Answer 11

C#, 82 80 bytes

-2 thanks to ceilingcat

With 2 dummy parameters (y and z).

(x,y,z)=>Enumerable.Range(1,y=(int)Math.Sqrt(x)).Sum(i=>2*i*(z=x/i)-z*~z+y*~y)/2

Try it online!

C#, 89 87 bytes

Single parameter.

x=>{int i=0,s=0,y=(int)Math.Sqrt(x),z;for(;i++<y;)s+=i*(z=x/i)+(y*~y-z*~z)/2;return s;}

Try it online!

Both use the same formula:

$$ \begin{eqnarray*} D(x) &=& \Big(\sum_{i=1}^{\lfloor\sqrt x\rfloor}i \cdot \Big\lfloor\frac x i\Big\rfloor + T(\Big\lfloor\frac x i\Big\rfloor) \ \Big) - \lfloor \sqrt x\rfloor \cdot T\big(\lfloor \sqrt x\rfloor \big)\\ &=& \Big(\sum_{i=1}^{y}i \cdot z + T(z) \ \Big) - y \cdot T(y)\\ &=& \sum_{i=1}^{y}i \cdot z + T(z) - T(y)\ \\ &=& \sum_{i=1}^{y}i \cdot z + \frac{z \cdot (z-1) - y \cdot (y-1) }{2} \\ \end{eqnarray*} $$ where $$ T(x) = \frac{x(x+1)}{2} \\ y = \lfloor\sqrt x\rfloor \\ z = \Big\lfloor\frac x i\Big\rfloor $$