Approximate summation of flooring function

Question

I have this summation:

$\sum_{k=0}^x \lfloor{\frac{k}{c}}\rfloor$

Do you have any ideas on any general expressions that can approximate this?

P.S I know I can approximate it with a Fourier expansion using $\{\frac{k}{c}\} = \frac{k}{c} \mod 1$, which is a sawtooth function, if I reform it to $\lfloor{\frac{k}{c}\rfloor}=\frac{k}{c}-\{\frac{k}{c}\}$. However, I'm looking for something more general, easier to handle and computationally more tractable.

$c$ is an integer btw which I will need to iterate over in another step of my algorithm.

Thank you.

Answer 1

With $c$ integer, an exact solution is easy.

From $k=0$ to $k=c-1$, the terms are $0$.

From $k=c$ to $k=2c-1$, the terms are $1$.

From $k=2c$ to $k=3c-1$, the terms are $2$.

...

Let $q=\lfloor\dfrac xc\rfloor$. You have full "periods" ($c$ equal terms) from $k=0$ to $cq-1$, then an incomplete period from $cq$ to $x$ inclusive.

The total is

$$c\cdot0+c\cdot1+c\cdot2\cdots c\cdot(q-1)+(x-cq+1)q=c\frac{(q-1)q}2+(x-cq+1)q.$$

Answer 2

With a given fixed value $c$, we have

$$\sum_{k=0}^x\left\lfloor\frac kc\right\rfloor=\sum_{k=c}^x\left\lfloor\frac kc\right\rfloor$$

and we can take this as a cue to the full result. In particular, let $q=\lfloor\frac xc\rfloor$, then we have result

$$\sum_{k=0}^x\left\lfloor\frac kc\right\rfloor= c\binom q2+q(x+1-qc)$$

Plugging in e.g. $x=c-1,c,c+1$ shows the correct outcomes.

EDIT:

Considering that there is interest in computational complexity, it is worthwhile to consider how the result can be manipulated to create a quantity that has the fewest possible computations, or how it can be adjusted to reduce the computation expense. In that vein, note that

$$c\binom q2-cq^2=c\frac{q^2-q}2-c\frac{2q^2}2=-c{q(q+1)\over 2}=-c\binom{q+1}2$$

so our modified result can be computed as

$$\sum_{k=0}^x\left\lfloor\frac kc\right\rfloor=q(x+1)-\frac{cq(q+1)}2$$

I have left the sum pieces undistributed (e.g., $q(x+1)$), but as the sums only involve increment by $1$, the "add first then multiply" efficiency is essentially non-existent.