What is the 1-case closed form for $\sum_{i = 1}^{x} \lfloor \frac{i - r}{d}\rfloor$?

Question

Let all untyped variables be natural numbers.

Formula?

Given $x \geq 1$, $0 \leq r \lt d$ there are two cases to handle: $x \lt r$ and $x \geq r$.

What is the 2-case closed form for $\sum_{i = 1}^{x} \lfloor \frac{i - r}{d}\rfloor$?

Attempt.

Case $x \lt r$. This implies that $1 \lt r$ so the terms are:

$$ \sum_{i=1}^x \left[\frac{i - r}{d}\right] = -\sum_{i=1}^x \lceil\frac{r - i}{d} \rceil $$

where $r \gt x \geq i \implies r \gt i$ so that the total is $-x$.

Thus for the case of $x \lt r$ we hace that the closed form is $-x$, because $r - i \lt d$ as well so the ceiling of any such fraction is $1$.

The other case is more difficult.

Case $x \geq r$. Let's look at the terms:

$$ \sum_{i = 1}^x \left[\frac{i - r}{d}\right] = \sum_{i = 1 - r}^{x - r} \left[\frac{i}{d}\right] = \sum_{i = 1 - r}^1 \left[\frac{i}{d}\right] + \sum_{i = 2}^{x-r} \left[\frac{i}{d}\right] \\ \ = \frac{d}{2}\left[\frac{x - r}{d}\right](\left[\frac{x-r}{d}\right] + 1) + (x - r - d\left[\frac{x-r}{d}\right] + 1)\left[\frac{x-r}{d}\right]- r + \delta_0(r) $$

 Question.

So my question is can the two cases be combined without resorting to $\{0,1\}$-valued symbols such as $[x \lt r]$ or $[x \geq r]$?

Answer 1

By modifying range of $i$ at the two ends:

• supplementing $\left\lfloor\frac{1-r}{d} \right\rfloor d \le i-r < 1-r$, where $\left\lfloor\frac{i-r}{d} \right\rfloor = \left\lfloor\frac{1-r}{d} \right\rfloor$; and

• removing $\left\lfloor \frac{x-r}d\right\rfloor d \le i-r \le x-r$, where $\left\lfloor\frac{i-r}{d} \right\rfloor = \left\lfloor\frac{x-r}{d} \right\rfloor$;

then the remaining number of terms is a multiple of $d$, with each partition of $d$ consecutive terms all having the same $\left\lfloor\frac{i-r}{d} \right\rfloor$.

$$\begin{align*} \sum_{i = 1}^{x}\left\lfloor\frac{i-r}{d} \right\rfloor &= \sum_{i = 1-r}^{x-r}\left\lfloor\frac{i}{d} \right\rfloor\\ &= \sum_{i = \left\lfloor\frac{1-r}{d} \right\rfloor d}^{\left\lfloor\frac{x-r}{d} \right\rfloor d -1} \left\lfloor\frac{i}{d} \right\rfloor - \sum_{i = \left\lfloor\frac{1-r}{d} \right\rfloor d}^{-r} \left\lfloor\frac{i}{d} \right\rfloor + \sum_{i = \left\lfloor \frac{x-r}d\right\rfloor d}^{x-r} \left\lfloor\frac{i}{d} \right\rfloor\\ &= \sum_{k= \left\lfloor\frac{1-r}{d} \right\rfloor}^{\left\lfloor \frac{x-r}d\right\rfloor -1} \sum_{i = kd}^{kd+d-1} \left\lfloor\frac{i}{d} \right\rfloor - \sum_{i = \left\lfloor\frac{1-r}{d} \right\rfloor d}^{-r} \left\lfloor\frac{i}{d} \right\rfloor + \sum_{i = \left\lfloor \frac{x-r}d\right\rfloor d}^{x-r} \left\lfloor\frac{i}{d} \right\rfloor\\ &= \sum_{k= \left\lfloor\frac{1-r}{d} \right\rfloor}^{\left\lfloor \frac{x-r}d\right\rfloor -1} \sum_{i = kd}^{kd+d-1} k - \sum_{i = \left\lfloor\frac{1-r}{d} \right\rfloor d}^{-r} \left\lfloor\frac{1-r}{d} \right\rfloor + \sum_{i = \left\lfloor \frac{x-r}d\right\rfloor d}^{x-r} \left\lfloor\frac{x-r}{d} \right\rfloor\\ &= \sum_{k= \left\lfloor\frac{1-r}{d} \right\rfloor}^{\left\lfloor \frac{x-r}d\right\rfloor -1} d k - \left(-r - \left\lfloor\frac{1-r}{d} \right\rfloor d + 1\right) \left\lfloor\frac{1-r}{d} \right\rfloor + \left(x-r - \left\lfloor \frac{x-r}d\right\rfloor d +1\right) \left\lfloor\frac{x-r}{d} \right\rfloor\\ &= \frac d2 \left(\left\lfloor \frac{x-r}d\right\rfloor - \left\lfloor\frac{1-r}d\right\rfloor\right) \left(\left\lfloor \frac{x-r}d\right\rfloor + \left\lfloor\frac{1-r}d\right\rfloor -1\right) - \left((1-r)\bmod d\right)\left\lfloor\frac{1-r}{d} \right\rfloor + \left(((x-r)\bmod d) +1\right) \left\lfloor\frac{x-r}{d} \right\rfloor\\ \end{align*}$$

(The $\bmod$ here returns the least non-negative remainder, regardless of the signs of $1-r$ and $x-r$.)