1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Lorenz H Menke Feb 7 at 18:31
  • $\begingroup$ I have tested this answer and it is correct. $\endgroup$ – Lorenz H Menke Feb 7 at 18:33
  • $\begingroup$ 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. $\endgroup$ – random Feb 7 at 18:50

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.