20
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I'm a bit confused as I would read "sub-linear time" as \$o\left(\log n\right)\$. not \$o\left(n\right)\$. \$\endgroup\$
    – tsh
    Commented Sep 12, 2023 at 7:24
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ Commented Sep 12, 2023 at 7:49

11 Answers 11

10
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 52 bytes: ->x{(1..$.=x**0.5).sum{(v=x/_1)*_1-(v*~v-$.*~$.)/2}} \$\endgroup\$ Commented Sep 12, 2023 at 4:10
9
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$
    – Neil
    Commented Sep 12, 2023 at 8:05
  • \$\begingroup\$ 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... \$\endgroup\$
    – Neil
    Commented Sep 12, 2023 at 8:15
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
}
\$\endgroup\$
5
  • \$\begingroup\$ What's %/%? Floor division? \$\endgroup\$ Commented Sep 11, 2023 at 16:28
  • \$\begingroup\$ @CommandMaster - yes. \$\endgroup\$ Commented Sep 11, 2023 at 17:37
  • 1
    \$\begingroup\$ 54 bytes, so long as %*% has the right time complexity \$\endgroup\$
    – Giuseppe
    Commented Sep 11, 2023 at 19:01
  • \$\begingroup\$ @Giuseppe - Beautiful: that's worthy of a separate post. \$\endgroup\$ Commented Sep 11, 2023 at 21:19
  • 1
    \$\begingroup\$ @Giuseppe - I had a shot at re-arrangement, too. Somehow it came out rather differently to yours, and happily one byte shorter... \$\endgroup\$ Commented Sep 12, 2023 at 7:47
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 41 38 bytes

 Nθ≔θη≔⁰ζWη«≔÷θιε≔÷θ⊕εη≧⁺×⁻ιη÷×ε⊕ε²ζ»Iζ

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.

 Nθ

Input \$ n \$.

≔θη

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

≔⁰ζ

Start with no total.

Wη«

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.

»Iζ

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – tsh
    Commented Sep 12, 2023 at 8:28
  • \$\begingroup\$ @tsh Nicely done! I tried to do something similar but I gave up. \$\endgroup\$
    – Arnauld
    Commented Sep 12, 2023 at 9:04
  • \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Commented Sep 12, 2023 at 9:33
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ You can drop the []s from [{-2!x*1+x}] (it will still fix that function as the x argument). \$\endgroup\$
    – coltim
    Commented Oct 26, 2023 at 20:04
1
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Suggest y*~y-z*~z instead of -z*~z+y*~y \$\endgroup\$
    – ceilingcat
    Commented Nov 3, 2023 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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