Una posibilidad es volver a escribir como $$M^2=(2N)^2+(N+1)^2. $$ So you are looking at the Pythagorean triples of the form $(N+1,2 N,M) $.
Edit: a lo Largo de las líneas de Erick queja, quiero hacer de esto una respuesta completa, así que vamos a hablar acerca de ternas Pitagóricas y cómo este se convierte en un aceptablemente rápido algoritmo.
Una terna Pitagórica primitiva es un triple $(r^2-s^2, 2rs, r^2+s^2)$ donde $r$ $s$ son coprime enteros positivos, no tanto extraño, y $r>s$. Resulta que cada terna Pitagórica -- un triple de enteros positivos $(a,b,c)$ donde $a^2+b^2=c^2$ - es un número entero múltiplo de una terna Pitagórica primitiva.
Si $(N+1, 2N, M)$ es una terna Pitagórica, entonces existen enteros positivos $r$, $s$, y $k$ por encima de donde $N+1=k(r^2-s^2)$$2N=2krs$. Desde $2N=2((N+1)-1)$, esto significa $2krs=2(k(r^2-s^2)-1)$, lo $krs=kr^2-ks^2-1$, lo $k(rs-r^2+s^2)=-1$. Desde $k$ es un entero positivo, esto significa $k=1$, por lo que un grado eliminado.
Así que estamos buscando a los enteros positivos $r$ $s$ donde $rs-r^2+s^2=-1$, o reorganizado, $s^2+rs-r^2+1=0$. Así que debe ser que $s=\frac{1}{2}\left(-r+\sqrt{r^2+4(r^2-1)}\right)=\frac{1}{2}\left(-r+\sqrt{5r^2-4}\right)$.
Tenga en cuenta que es $+$, no $\pm$, en el de arriba, debido a $s$ debe ser positivo. Por lo tanto, dado $r$, podemos encontrar $s$.
De manera que el algoritmo es ahora este. Para cada entero positivo $r$, encontramos a $s$ en la anterior. Si es un entero positivo, entonces $N=rs$, y ha encontrado una solución a $N$. Cada $N$ es de esta forma, por lo que este enumera todos ellos, en fin.
Además, si algún número $N$ es una solución, este algoritmo se encuentra en $O(\sqrt{N})$ del tiempo.
Se puede acelerar mediante la enumeración de soluciones para la Pell-como la ecuación de $5r^2-4=t^2$ (es decir, la búsqueda de $r$ hacer $s$ racional), que se puede hacer muy rápidamente a través de una recurrencia (creo) pero yo en realidad no sé cómo hacerlo. Si usted puede hacer que, alrededor de la mitad de los $r$ hacer $s$ un entero, en oposición a simplemente racional, y usted tiene realmente un algoritmo rápido.
