The closed form of a sum of mod(k,m) where k goes from 1 to a arbitrary number.

Question

Is there a closed form for $\sum_{n=0}^{C} mod(n,m)$ for arbitrary integers m ?

Answer 1

I’m assuming that you mean what I’d write as $\sum_{n=0}^C(n\bmod m)$, where $n\bmod m$ is the unique integer in $\{0,\ldots,m-1\}$ congruent to $n$. Let $f(C)=\sum_{n=0}^C(n\bmod m)$.

Note first that

$$f(m-1)=\sum_{n=0}^{m-1}(n\bmod m)=\frac{m(m-1)}2\;.$$

Let $C=qm+r$, where $r=C\bmod m$. Then $q=\left\lfloor\frac{C}m\right\rfloor$, and $r=C-mq=C-m\left\lfloor\frac{C}m\right\rfloor$, so

$$\begin{align*} f(C)&=\frac12m(m-1)q+\sum_{k=0}^rk\\\\ &=\frac12\big(m(m-1)q+r(r+1)\big)\\\\ &=\frac12\Big(m(m-1)q+(C-mq)(C-mq+1)\Big)\\\\ &=\frac12\Big((m-1)(C-r)+r(r+1)\Big)\;, \end{align*}$$

where I’ve given it both in terms of $q$ and in terms of $r$.