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

ceiling-and-floor-functionsclosed-formelementary-number-theorysummation

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\}$.

Best 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$$

Related Question