Krdytkyu

I'd like to calculate $f(n,m)=sumlimits_{i=1}^{n-1}sumlimits_{j=1}^{m-1} |mi-nj|$ for all $1 leq n leq N, 1 leq m leq M$. Straightforward brute force method runs in $O(N^2M^2)$ which is too slow. How to calculate all values in $O(NM)$?

We show the following is valid for positive integers $n,m$:
begin{align*}
sum_{i=1}^{n-1}sum_{j=1}^{m-1}|mi-nj|=frac{1}{6}left(2m^2n^2-3m^2n+m^2-3mn^2+3mn+n^2-left(gcd(m,n)right)^2right)
end{align*}

In the following we denote with $d=gcd(m,n)$.

We obtain
begin{align*}
color{blue}{sum_{i=1}^{n-1}}&color{blue}{sum_{j=1}^{m-1}|mi-nj|}tag{2}\
&=2sum_{i=1}^{n-1}sum_{j=1}^{lfloor mi/nrfloor}(mi-nj)tag{3}\
&=2msum_{i=1}^{n-1}isum_{j=1}^{lfloor mi/nrfloor}1-2nsum_{i=1}^{n-1}sum_{j=1}^{lfloor mi/nrfloor}j\
&=2msum_{i=1}^{n-1}ileftlfloorfrac{m}{n}irightrfloor
-nsum_{i=1}^{n-1}leftlfloorfrac{m}{n}irightrfloorleft(leftlfloorfrac{m}{n}irightrfloor+1right)tag{4}\
&=sum_{i=1}^{n-1}left(2mi-nleftlfloorfrac{m}{n}irightrfloor-nright)leftlfloorfrac{m}{n}irightrfloortag{5}\
&=sum_{i=1}^{n-1}left(2mi-nleft(frac{m}{n}i-left{frac{m}{n}iright}right)-nright)left(frac{m}{n}i-left{frac{m}{n}iright}right)tag{6}\
&=nsum_{i=1}^{n-1}left(frac{m^2}{n^2}i^2-left{frac{m}{n}iright}^2-frac{m}{n}i+left{frac{m}{n}iright}right)\
&=frac{m^2}{n}sum_{i=1}^{n-1}i^2-nsum_{i=1}^{n-1}left{frac{m}{n}iright}^2-msum_{i=1}^{n-1}i+nsum_{i=1}^{n-1}left{frac{m}{n}iright}\
&=frac{m^2}{n}frac{1}{6}(n-1)n(2n-1)-ndsum_{i=0}^{n/d-1}left(frac{d}{n}iright)^2\
&qquad -mfrac{1}{2}(n-1)n+ndsum_{i=0}^{n/d-1}left(frac{d}{n}iright)tag{7}\
&=frac{1}{6}m^2(n-1)(2n-1)-frac{d^3}{n}frac{1}{6}left(frac{n}{d}-1right)frac{n}{d}left(frac{2n}{d}-1right)\
&qquad-frac{1}{2}mn(n-1)+d^2frac{1}{2}left(frac{n}{d}-1right)frac{n}{d}tag{8}\
&,,color{blue}{=frac{1}{6}left(2m^2n^2-3m^2n+m^2-3mn^2+3mn+n^2-d^2right)}
end{align*}
and the claim (1) follows.

Comment:

• In (3) we use that positive and negative parts in (2) correspond to each other.




• In (4) we expand the inner sums.




• In (5) we rearrange the terms and factor out $leftlfloorfrac{m}{n}irightrfloor$.




• In (6) we rewrite the expression using the fractional part ${x}=x-lfloor xrfloor$ of $x$.




• In (7) we expand the sums with linear and quadratic terms and we apply the identity
  begin{align*}
  sum_{i=1}^{n}fleft(left{frac{m}{n}iright}right)=dsum_{i=0}^{n/d-1}fleft(frac{d}{n}iright)
  end{align*}
  where $d=gcd(m,n)$.




• In (8) we expand the sums and simplify the expression in the final step.

Given $n$ and $mgeq n$ you can determine the numbers
$$r_{nm}(j):=leftlfloor{m jover n}rightrfloorqquad(1leq jleq n-1)$$in $O(n)$ steps, and another $O(n)$ steps then compute
$$f(n,m)=sum_{j=1}^{n-1}r_{nm}(j)bigl(2 m j-n(r_{nm}(j)+1)bigr) .tag{1}$$
One arrives at this formula after observing that by symmetry it is sufficient to consider the lattice points $(j,k)$ below the line $y={mover n}x$. Look at these lattice points on the ordinate $x=j$. Their $y$-coordinates $k$ run through the set $[r_{nm}(j)]$. The"integrand" $p(j,k):=|m j-n k|=mj -n k$ produces an arithmetic progression on these lattice points. Therefore the sum of the $p$-values along the ordinate $x=j$ is their number $r_{nm}(j)$, times the arithmetic mean of the first and the last $p$-values. This leads to formula $(1)$.