= Euclidean floor-sum transformation
{c}
For integers $n\geq0$, $m>0$, write $F(n,a,b,m)=\sum_{i=0}^{n-1}\lfloor(ai+b)/m\rfloor$. <Euclidean division> gives $a=qm+r$ and $b=sm+t$, with $0\leq r,t<m$, hence
$$
F(n,a,b,m)=q\frac{n(n-1)}2+sn+F(n,r,t,m).
$$
For $0<a<m$ and $0\leq b<m$, put $y=an+b$. Interchanging the two axes in the remaining <lattice point> problem gives
$$
F(n,a,b,m)=F(\lfloor y/m\rfloor,m,y\bmod m,a).
$$
If $y<m$, the original sum is zero; if $a=0$ after reduction, it is also zero. Each swap lowers the modulus as in the <Euclidean algorithm>, enabling logarithmically many reduction stages. For example $F(5,3,1,7)=3$, and the swapped sum $F(2,7,2,3)=0+3$ gives the same answer.
Back to article page
