# Sums of sum of divisors in sublinear time

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.

• I'm a bit confused as I would read "sub-linear time" as $o\left(\log n\right)$. not $o\left(n\right)$.
– tsh
Sep 12 at 7:24
• @tsh It's specified that $n$ is the input, not the number of digits in the input. If you think it would be helpful I can add that as a note. "Sublinear time" seems to be an accepted term for this runtime in computational number theory Sep 12 at 7:49

# 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! • 52 bytes: ->x{(1..$.=x**0.5).sum{(v=x/_1)*_1-(v*~v-$.*~$.)/2}} Sep 12 at 4:10

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

• Yes, this is the same as my approach, although obviously I loop downwards, and I don't have the insight to understand your rearrangement, which is annoying as it would probably save me a few bytes. (And I would use T for triangular numbers rather than F which I associate with Fibonacci numbers.)
– Neil
Sep 12 at 8:05
• The sequence of aᵢ is the same as the sequence of ⌊n/aᵢ⌋ so it does my brain in that the sums are the same...
– Neil
Sep 12 at 8:15

# 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.

# 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/_$-;~$/*+$~$~$;$ !\$,_*

# R, 6151 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
}

• What's %/%? Floor division? Sep 11 at 16:28
• @CommandMaster - yes. Sep 11 at 17:37
• 54 bytes, so long as %*% has the right time complexity Sep 11 at 19:01
• @Giuseppe - Beautiful: that's worthy of a separate post. Sep 11 at 21:19
• @Giuseppe - I had a shot at re-arrangement, too. Somehow it came out rather differently to yours, and happily one byte shorter... Sep 12 at 7:47

# 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!

# 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 \$$.

≔⁰ζ


Ｗη«


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) \$$.

# 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.

# 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

Expects a BigInt.

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


Try it online!

• f=(n,q=n)=>q&&(i=n/q)*(q-n/++i)*i/2n+f(n,n/i) -- I have no idea why it works. Just modified from the 48 bytes version by try and error.
– tsh
Sep 12 at 8:28
• @tsh Nicely done! I tried to do something similar but I gave up. Sep 12 at 9:04
• @tsh I've ported @‌dingledooper's final formula (I was originally using a formula equivalent to an earlier one in his answer) to my answer and it now comes to the same calculation as your golf.
– Neil
Sep 12 at 9:33

# 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

Try it online!

• You can drop the []s from [{-2!x*1+x}] (it will still fix that function as the x argument). Oct 26 at 20:04

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

• Suggest y*~y-z*~z instead of -z*~z+y*~y Nov 3 at 7:22