Floor sum

A floor sum adds values of a floor function, often in the form $F(n,a,b,m)={\sum }_{i=0}^{n-1}\lfloor (ai+b)/m\rfloor$ for integers $n\ge 0$, $m>0$, $a$, and $b$. If $a,b\ge 0$, it counts lattice points $(i,j)$ with $0\le i<n$ and $1\le j\le (ai+b)/m$. Splitting $a$ and $b$ into quotients and remainders isolates an arithmetic progression and a constant contribution; swapping the remaining counting axes leads to an Euclidean algorithm reduction.

For an arithmetic function $a$, changing the order of the finite summation gives ${\sum }_{d=1}^{n}a(d)\lfloor n/d\rfloor ={\sum }_{t=1}^n{\sum }_{d\le \lfloor n/t\rfloor }a(d)$. Both sides count pairs of positive integers $(d,t)$ with $dt\le n$, assigning weight $a(d)$ to each pair. This expresses a weighted floor sum in terms of a summatory function.

For integers $n\ge 0$, $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\le r,t<m$, henceFor $0<a<m$ and $0\le b<m$, put $y=an+b$. Interchanging the two axes in the remaining lattice point problem givesIf $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.