7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – GH from MO Jan 31 '15 at 10:34
  • $\begingroup$ I mean the positive remainder (e.g. 7 modulo 4 = 3) $\endgroup$ – Noureldin Yosri Jan 31 '15 at 10:39
  • $\begingroup$ Sorry for skidding off topic, but where could I find out more about $\sum{\big(\frac{N}{i}-\lfloor\frac{N}{i}\rfloor\big)}$? $\endgroup$ – Yaakov Baruch Mar 23 '15 at 20:19
17
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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