How to calculate the sum of remainders of N?

Question

I'm trying to sum the remainders when dividing N by numbers from $1$ up to $N$ $$\sum_{i = 1}^{N} N \bmod i$$

It's easy to write a program to evaluate the sum if N is small in $O(N)$ but what if N is large ~ 1e10

so I was wondering if there is a formula or an algorithm to get the sum in a better way than $O(N) $.

I searched online and found a paper which drives some interesting properties of the sum yet doesn't state an efficient way to compute it although it contains a recursive formula yet that formula isn't practical since it reduced the problem from $N$ to $N-1$ and the relationship contains $\sigma (n)$ which can be evaluated at best in $O$(#prime factors of $N$) resulting in a much worse time than $O(N)$

on the other hand the paper contains the formula $$ \sum_{i = 1}^{N} N \bmod i = N^{2} - \sum_{i = 1}^{N} \sigma (i) $$

so if I can evaluate the sum of the sum-of-divisors function I would get the answer, yet I searched online and found only this discussion which had a formula for the sum of the sum-of-divisors function yet it's not exact and contains the sum of fractions which introduce rounding errors

so I was wondering if there is a way to evaluate any of the two sums exactly and in a better time complexity than $O(N)$.

Answer 1

One can use the Dirichlet hyperbola method to compute $\sum_{i \leq n} \sigma(i)$ in time $O( n^{1/2} )$ (up to logarithmic factors coming from arithmetic operations such as division):

\begin{align} \sum_{i \leq n} \sigma(i) &= \sum_{i \leq n} \sum_{d|i} d \\ &= \sum_{d,m: dm \leq n} d \\ &= \sum_{d \leq \sqrt{n}} d \sum_{\sqrt{n} < m \leq n/d} 1 + \sum_{m \leq \sqrt{n}} \sum_{d \leq n/m} d \\ &= \sum_{d \leq \sqrt{n}} d( \lfloor \frac{n}{d} \rfloor - \lfloor \sqrt{n}\rfloor ) + \sum_{m \leq \sqrt{n}} \frac{\lfloor\frac{n}{m}+1\rfloor \lfloor \frac{n}{m} \rfloor}{2}. \end{align}

One can obtain some small speedups (by a factor of $O(1)$) by collecting some like terms here.

One can improve this to $O(n^{1/2-c})$ for some small $c>0$ by approximating the hyperbola by a polygon: see the Polymath4 paper in which this was done for the sum $\sum_{i\leq n} \tau(i)$. Other than small improvements in $c$, I think this is the fastest algorithm currently known.

Answer 2

I found an article from Richard Sladkey, "A Successive Approximation Algorithm for computing the Divisor Summary Function", June 18, 2012 arXiv:1206.3369v1 [math.NT] 15 June 2012 where he shows that the solution can be computed in $\mathcal{O}(N^{1/3})$ steps. The paper introduces restricted divisor sums for part of this calculation.

Answer 3

According to the references in OEIS there isn't fast way unless I have missed something.

The fastest I saw is $a(n+1) = a(n) + 2n+1 - \sigma(n+1) $.