I want to compute

$$\sum_{i=a}^b \left\lfloor \frac{i}{k} \right\rfloor$$

Where $k < b < \infty$, and $a > 0$. I don't know where to begin (or if there's a closed form, for that matter), so any hints would be appreciated!

  • $\begingroup$ A good beginning point would be to consider some values of $a$, $b$, and $k$ that include the following cases: $b=nk$, $b=nk+r$, $a=mk$, $a=mk+s$. This will give you an idea for exactly what you are summing. $\endgroup$ – Terra Hyde Jul 31 '15 at 5:50

Start with what we know: $\lfloor\frac{i}{k}\rfloor$ is the same as the computer science integer divide. That is, it gives us the whole part of long division and drops the remainder.

Next, we know that every whole number will appear at most $k$ times, since that is how many fractions exist between $0$ and $1$ and have denominator $k$ (excluding one endpoint).

Next, $\lfloor\frac{b}{k}\rfloor-\lfloor\frac{a}{k}\rfloor$ tells us how many whole numbers we will see at least once each.

What you end up with is $$\left(k\sum\limits_{i=\left\lceil\frac{a}{k}\right\rceil}^{\left\lfloor\frac{b}{k}\right\rfloor}i\right)+\left(r(b,k)\left\lfloor\frac{b}{k}\right\rfloor\right)+\left((k-r(a,k))\left\lfloor\frac{a}{k}\right\rfloor\right)$$

The first term in this accounts for all the whole numbers that appear exactly $k$ times. The second term accounts for the highest integers that appear, and similarly for the final term with the lowest integers. The function $r(x,y)$ here represents the remainder in the division $x/y$.

The first term can be simplified using the fact that $$\sum\limits_{i=1}^ni=\frac{n(n+1)}{2}$$ so that the result is $$k\left(\frac{\left\lfloor\frac{b}{k}\right\rfloor\left(\left\lfloor\frac{b}{k}\right\rfloor+1\right)-\left\lceil\frac{a}{k}\right\rceil\left(\left\lceil\frac{a}{k}\right\rceil-1\right)}{2}\right)+\left(r(b,k)\left\lfloor\frac{b}{k}\right\rfloor\right)+\left((k-r(a,k))\left\lfloor\frac{a}{k}\right\rfloor\right)$$

With any luck, this makes sense and isn't completely stupid.


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.