Encontrar una forma cerrada para $\sum\limits_{\substack{0\le n\le N\\0\le m\le M}}\left|nM-Nm\right|$

Question

Estoy tratando de averiguar si hay una forma cerrada para la siguiente suma: $$ \sum_{\substack{0\le n\le N \\ 0\le m\le M}}\left|(N-n)(M-m)-nm\right|=\sum_{\substack{0\le n\le N \\ 0\le m\le M}}\left|nM-Nm\right|. $$ Claramente, de la simetría, si queremos eliminar los valores absolutos, la suma evaulates a $0$.

El uso de la simetría, traté de evaluar la suma como $$ 2\cdot\sum_{\substack{0\le n\le N \\ 0\le m\le M \\ (N-n)(M-m)\gt nm}}\left((N-n)(M-m)-nm\right). $$ Sin embargo, que la expresión terminó contiene sumas de piso funciones, para que no sabía una forma cerrada.

Hay otra manera de obtener una forma cerrada para la anterior suma?

---

Edit: Si no hay forma cerrada puede ser provisto de un algoritmo eficiente para calcular dicha suma, dado $N,M$ también sería bueno.

---

Edit 2: Ya que el tiempo que he colocado la recompensa, yo era capaz de encontrar una forma cerrada para la suma:

$$\frac{1}{6}\left[MN(2 M N + 3 (M + N + 1)) + M^2 + N^2-\gcd(M,N)^2\right].$$

Así que ahora puedo cambiar la pregunta a un desafío: se derivan de la forma anterior de la suma. La más bonita de derivación (si hay alguna) será obtener la recompensa.

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$Supongamos $M, N > 0$ y $d = (M, N)$, $M = md$, $N = nd$.\begin{align*} \sum_{\substack{0\leqslant k\leqslant M\\0\leqslant j\leqslant N}} |kN - jM| &= \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1}} |kN - jM| + \sum_{k = 0}^{M - 1} (NM - kN) + \sum_{j = 0}^{N - 1} (MN - jM)\\ &= \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1}} |kN - jM| + \frac{1}{2} NM(M + 1) + \frac{1}{2} MN(N + 1). \tag{1} \end{align*} Tenga en cuenta que$$ \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1}} (kN - jM) = \frac{1}{2} NM(M - 1) - \frac{1}{2} MN(N - 1), $$ a continuación,\begin{align*} \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1}} |kN - jM| &= \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1\\kN\geqslant jM}} (kN - jM) - \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1\\kN<jM}} (kN - jM)\\ &= 2\sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1\\kN\geqslant jM}} (kN - jM) - \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1}} (kN - jM) \end{align*} lo que implica$$ (1) = 2\sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1\\kN\geqslant jM}} (kN - jM) + MN(N + 1). \etiqueta{2} $$

Ahora, para cada una de las $0 \leqslant k \leqslant M - 1$, definir $$r_k = kn - m\left[ \dfrac{kn}{m} \right],$$ i.e. $r_k$ is the remainder of $kn$ modulo $m$. \begin{align*} &\peq \sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1\\kN\geqslant jM}} (kN - jM) = \sum_{\substack{0\leqslant k\leqslant dm-1\\0\leqslant j\leqslant dn-1\\kdn\geqslant jdm}} (kdn - jdm) = d \sum_{\substack{0\leqslant k\leqslant dm-1\\0\leqslant j\leqslant dn-1\\kn\geqslant jm}} (kn - jm)\\ &= d\sum_{k = 0}^{dm - 1} \sum_{j = 0}^{\left[ \frac{kn}{m} \right]} (kn - jm) = d\sum_{k = 0}^{dm - 1} \left( kn \left( \left[ \frac{kn}{m} \right] + 1 \right) - m·\frac{1}{2} \left[ \frac{kn}{m} \right] \left( \left[ \frac{kn}{m} \right] + 1 \right) \right)\\ &= d\sum_{k = 0}^{dm - 1} \left( kn - \frac{m}{2} \left[ \frac{kn}{m} \right] \right) \left( \left[ \frac{kn}{m} \right] + 1 \right) = d\sum_{k = 0}^{dm - 1} \left( kn - \frac{m}{2}·\frac{kn - r_k}{m} \right) \left( \frac{kn - r_k}{m} + 1 \right)\\ &= d\sum_{k = 0}^{dm - 1} \left( \frac{1}{2} kn + \frac{1}{2} r_k \right) \left( \frac{kn}{m} + 1 - \frac{r_k}{m} \right) = \frac{d}{2m} \sum_{k = 0}^{dm - 1} (kn(kn + m) + m r_k - r_k^2). \tag{3} \end{align*}

Tenga en cuenta que $(m, n) = 1$ implica que para cada $0 \leqslant s \leqslant d - 1$,$$\{kn \mid sm \leqslant k \leqslant (s + 1)m - 1\}$$ is a complete residue system modulo $m$, therefore$$ \{r_{sm}, \cdots, r_{(s + 1)m - 1}\} = \{ 0, \cdots, m - 1\}. $$ Por lo tanto$$ \sum_{k = 0}^{dm - 1} r_k = \sum_{s = 0}^{d - 1} \sum_{k = sm}^{(s + 1)m - 1} r_k = \sum_{s = 0}^{d - 1} \sum_{k = 0}^{m - 1} k = \frac{1}{2} m(m - 1)·d,\\ \sum_{k = 0}^{dm - 1} r_k^2 = \sum_{s = 0}^{d - 1} \sum_{k = 0}^{m - 1} r_k^2 = \sum_{s = 0}^{d - 1} \sum_{k = 0}^{m - 1} k^2 = \frac{1}{6} (2m - 1)(m - 1)m·d, $$ a continuación,\begin{align*} (3) &= \frac{d}{2m} \sum_{k = 0}^{dm - 1} kn(kn + m) + \frac{d}{2} \sum_{k = 0}^{dm - 1} r_k - \frac{d}{2m} \sum_{k = 0}^{dm - 1} r_k^2\\ &= \frac{dn^2}{2m} \sum_{k = 0}^{dm - 1} k^2 + \frac{1}{2} dn \sum_{k = 0}^{dm - 1} k + \frac{d}{2} × \frac{1}{2} m(m - 1)·d - \frac{d}{2m} × \frac{1}{6} (2m - 1)(m - 1)m·d\\ &= \frac{dn^2}{2m} × \frac{1}{6} (2dm - 1)(dm - 1)dm + \frac{1}{2} dn × \frac{1}{2} (dm - 1)dm\\ &\peq + \frac{d}{2} × \frac{1}{2} m(m - 1)·d - \frac{d}{2m} × \frac{1}{6} (2m - 1)(m - 1)m·d\\ &= \frac{1}{6} d^4 m^2 n^2 + \frac{1}{4} d^3 mn(m - n) + \frac{1}{12} d^2 (m^2 + n^2 - 3mn) - \frac{1}{12} d^2. \end{align*}

La combinación con (2),\begin{align*} \sum_{\substack{0\leqslant k\leqslant M\\0\leqslant j\leqslant N}} |kN - jM| &= 2\sum_{\substack{0\leqslant k\leqslant M-1\\0\leqslant j\leqslant N-1\\kN\geqslant jM}} (kN - jM) + MN(N + 1)\\ &= 2\left( \frac{1}{6} d^4 m^2 n^2 + \frac{1}{4} d^3 mn(m - n) + \frac{1}{12} d^2 (m^2 + n^2 - 3mn) - \frac{1}{12} d^2 \right)\\ &\peq + d^2 mn(dn + 1)\\ &= \frac{1}{3} d^4 m^2 n^2 + \frac{1}{2} d^3 mn(m + n) + \frac{1}{6} d^2 (m^2 + n^2 + 3mn) - \frac{1}{6} d^2\\ &=\frac{1}{6} \left( MN(2MN + 3(M + N + 1)) + M^2 + N^2-(M,N)^2\right). \end{align*}

Answer 2

La integridad, aquí está mi propia derivación:

En primer lugar, dado $d:=\gcd(M,N)$, $\,N':= N/d$, se tiene la siguiente identidad: $$ \sum_{n=0}^{N}f\left(\left\{n\frac{M}{N}\right\}\right) =f\left(0\right)+d\sum_{n=0}^{N'-1}f\left(\frac{n}{N}\right) $$ Quitando el valor absoluto dará una suma que equivale a $0$. Por lo tanto, la parte positiva de la suma es igual a la parte negativa. Por lo tanto: $$ \begin{equation} \begin{split} \sum_{n=0}^N\sum_{m=0}^M\left|nM-Nm\right| &= 2\sum_{n=0}^N\sum_{m=0}^{\left\lfloor n\frac{M}{N}\right\rfloor}\left(nM-Nm\right) \\ &=\sum_{n=0}^N\left(2\left(\left\lfloor n\frac{M}{N}\right\rfloor+1\right)nM-N\left(\left\lfloor n\frac{M}{N}\right\rfloor^2+\left\lfloor n\frac{M}{N}\right\rfloor\right)\right) \\ &=\sum_{n=0}^N\left(\left\lfloor n\frac{M}{N}\right\rfloor+1\right)\left(2nM-N\left\lfloor n\frac{M}{N}\right\rfloor\right) \\ &=\sum_{n=0}^N\left(n\frac{M}{N}-\left\{ n\frac{M}{N}\right\}+1\right)\left(nM+N\left\{ n\frac{M}{N}\right\}\right) \\ &=\sum_{n=0}^N\left(n^2\frac{M^2}{N}+nM-N\left\{ n\frac{M}{N}\right\}^2+N\left\{ n\frac{M}{N}\right\}\right) \\ &=\small{\frac{1}{6}\left((N+1)(2N+1)M^2+3N(N+1)M-Nd\frac{(N'-1)(2N'-1)}{N'}+3Nd(N'-1)\right)} \\ &=\small{\frac{1}{6}\left((N+1)(2N+1)M^2+3N(N+1)M-(N-d)(2N-d)+3N(N-d)\right)} \\ &=\frac{1}{6}\left(MN(2MN + 3(M+N+1)) +M^2 +N^2-d^2\right) \end{split} \end{equation} $$

Answer 3

Sugerencia:

El problema se rige por las soluciones de $Mn=Nm$, el principal de la diagonal del rectángulo. WLOG $M\ge N$ y supongamos por ahora que $M,N$ son relativas de los números primos, por lo que la igualdad sólo se produce en las esquinas.

Por simetría, sólo miramos por debajo de la diagonal y para una determinada $m$,

$$0\le n\le\left\lfloor{\frac{Nm}M}\right\rfloor=\left\lfloor{Qm}\right\rfloor.$$

A continuación,

$$S:=\sum_{m=0}^{M-1}\sum_{n=0}^{\left\lfloor{Qm}\right\rfloor}(Nm-Mn)=M\sum_{m=0}^{M-1}\sum_{n=0}^{\left\lfloor{Qm}\right\rfloor}(Qm-n)\\ =M\sum_{m=0}^{M-1}\left(Qm-\frac12\left\lfloor{Qm}\right\rfloor\right)\left(\left\lfloor{Qm}\right\rfloor+1\right)\\ =\frac M2\sum_{m=0}^{M-1}\left(Qm+\{Qm\}\right)\left(Qm-\{Qm\}+1\right)\\ =\frac M2\sum_{m=0}^{M-1}\left((Qm)^2+Qm-\{Qm\}^2+\{Qm\}\right).$$

Como en las sumas de fracciones, todas las fracciones de los $0/M$ $(M-1)/M$aparecen (en desorden),

$$12S=6M\left(Q^2\frac{(M-1)M(2M-1)}6+Q\frac{(M-1)M}2-\frac{(M-1)M(2M-1)}{6M^2}+\frac{(M-1)M}{2M}\right)\\ =2M^2N^2+M^2-3MN^2-3MN+N^2+3NM^2-1.$$

Para esto, tenemos que añadir la omitido plazo ($m=M$), que se encuentra para ser

$$T:=\sum_{n=0}^{N}(NM-Mn)=\frac{MN(N+1)}2,$$

y, finalmente,

$$2(S+T)=\frac{2M^2N^2+M^2+9MN^2+9MN+N^2+3NM^2-1}6.$$

Ahora si $M,N$ no están relativa de los números primos, uno puede dividir la suma de $G=\gcd(M,N)$ subsums de $\dfrac MG$ términos y un final $M^{th}$ plazo. Esto equivale a la sustitución de la final de la $-1$$-G^2$.

Answer 4

Solución parcial:

Podemos romper la expresión en cuatro partes $E_1 + E_2 + E_3 + E_4$

donde $$E_1 = \sum_{\substack{0\le n\le N/2 \\ 0\le m\le M/2}}(MN -mN-nM) = $$ $$E_2 = \sum_{\substack{0\le n\le N/2 \\ M/2\le m\le M}}|MN -mN-nM|$$ $$E_3 = \sum_{\substack{N/2\le n\le N \\ 0\le m\le M/2}}|MN -mN-nM|$$ $$E_4 = \sum_{\substack{N/2\le n\le N \\ M/2\le m\le M}}(mN + nM - MN) = \sum_{\substack{0\le n\le N/2 \\ 0\le m\le M/2}}(mN + nM)$$

$E_1 + E_4 = M^2N^2/4$

Tanto en $E_2$ $E_3$ puede escribirse como

$$ E_2 = E_3 = \sum_{\substack{0\le n\le N/2 \\ 0\le m\le M/2}}|MN/2 -mN-nM|$$

por lo $$E_2 + E_3 = \sum_{\substack{0\le n\le N/2 \\ 0\le m\le M/2}}|MN -2mN-2nM|$$

Por lo $$LHS = M^2N^2/4 + \sum_{\substack{0\le n\le N/2 \\ 0\le m\le M/2}}|MN -2mN-2nM|$$ y puede ser que de forma recursiva puede avanzar?