# How to calculate the sum of remainders of N?

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

• Please use TeX properly on this site. Also, it is not clear what you mean by "reminder" as there are different conventions around (e.g. the residue of 7 modulo 4 equals -1). – GH from MO Jan 31 '15 at 10:34
• I mean the positive remainder (e.g. 7 modulo 4 = 3) – Noureldin Yosri Jan 31 '15 at 10:39
• Sorry for skidding off topic, but where could I find out more about $\sum{\big(\frac{N}{i}-\lfloor\frac{N}{i}\rfloor\big)}$? – Yaakov Baruch Mar 23 '15 at 20:19

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):
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.
The fastest I saw is $a(n+1) = a(n) + 2n+1 - \sigma(n+1)$.