# Express $\sum_{a=1}^{p-1} \lfloor{(v+qa)/p}\rfloor$ in closed form.

Here $$p$$ and $$q$$ are primes but likely not necessary for the answer. Also $$p < q$$ and $$v\in\left\{{0,1,\dots,p*q-1}\right\}$$. This problem arises from counting the number of reducible quadratics of the form $$(p*x+a)(q*x+b)$$. I have found closed form expression for all the terms except this one. See Evaluation of the sum $\sum_\limits{a=1}^{p-1} \left\lfloor \frac{\left\lfloor{v/p}\right\rfloor+a}{q}\right\rfloor$ for the evaluation of the case where we would have $$q=1$$ and $$v \rightarrow \lfloor{v/p}\rfloor$$ and $$\lfloor{v/p}\rfloor \in \left\{{0,1,\dots,q-1}\right\}$$. Note that the upper limit of this sum in the title should be $$q-1$$ which is corrected in the analysis. Thus the correct solution for this reference is $$\sum_{a=1}^{p}\lfloor{(\lfloor{v/p}\rfloor+a)/p}\rfloor = \lfloor{v/p}\rfloor$$.

I can factor the $$q$$ which gives $$\sum_{a=1}^{p-1} \lfloor{q(\frac{(v/q+a)}{p}})\rfloor$$

An approximate estimate from using the floor function product formula is that this sum $$\ge q * \lfloor{v/q}\rfloor$$ where in this case $$\lfloor{v/q}\rfloor \in \left\{{0,1,\dots,p-1}\right\}$$.

## 1 Answer

From the equivalence of $$v+a_1q\equiv v+a_2q \pmod p$$ with $$p\mid (a_2-a_1)q$$ and therefore with $$p\mid a_2-a_1$$, it follows that $$p$$ successive values of $$a$$ give $$p$$ different rounding losses $$\frac jp=\frac{v+qa}p-\Bigl\lfloor{\frac{v+qa}p}\Bigr\rfloor$$, so $$\sum_{a=0}^{p-1} \Bigl\lfloor\frac{v+qa}p\Bigr\rfloor =\sum_{a=0}^{p-1} \frac{v+qa}p -\sum_{j=0}^{p-1} \frac jp=v+\frac{p-1}2q-\frac{p-1}2 \quad\text{ and}$$ $$\sum_{a=1}^{p-1} \Bigl\lfloor\frac{v+qa}p\Bigr\rfloor = v+\frac12(p-1)(q-1)-\Bigl\lfloor\frac{v}p\Bigr\rfloor$$

• Do you mean the equivalence of $v + a1\, q (\text{mod } p) \equiv v + a2\, q (\text{mod } p)$ or $(v + a1\, q) (\text{mod } p) \equiv (v + a2\, q) (\text{mod } p)$? – Lorenz H Menke Feb 7 at 18:31
• I have tested this answer and it is correct. – Lorenz H Menke Feb 7 at 18:33
• I meant the logical equivalence of the statements $v+a_1q\equiv v+a_2q \pmod p$ and $p\mid (a_2-a_1)q$ (and $p\mid a_2-a_1$ ). The validity of one of the statements implies the validity of the other two. – random Feb 7 at 18:50