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](http://math.pugetsound.edu/~mspivey/RemaindersFinal.pdf) 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](https://mathoverflow.net/questions/100027/sum-of-the-sum-of-divisors-function) 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)$.



How to calculate the sum of remainders of N?
One can use the [Dirichlet hyperbola method](http://planetmath.org/dirichlethyperbolamethod) 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](http://www.ams.org/mathscinet-getitem?mr=2869058) 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.


