Número entero de soluciones de $x^2 + y^2 = k$

Question

Estoy buscando algo de ayuda refutar una respuesta a una pregunta de StackOverflow que he publicado acerca de la computación en el número de doble plaza combinaciones para un entero dado.

La pregunta original es de el Facebook Hacker Cup

Fuente: Facebook Hacker Cup La Calificación De La Ronda De 2011

Un doble-cuadrado número es un entero $X$ que puede ser expresado como la suma de dos cuadrados perfectos. Por ejemplo, 10 es un doble cuadrado debido a $10 = 3^2 + 1^2$. Dado $X$, ¿cómo podemos determinar el número de maneras en que puede ser escrito como la suma de dos cuadrados? Para ejemplo, $10$ sólo puede ser escrito como $3^2 + 1^2$ (no contamos $1^2 + 3^2$ como ser diferente). Por otro lado, $25$ puede ser escrito como $5^2 + 0^2$ o como $4^2 + 3^2$.

Usted necesita para resolver este problema para $0 \leq X \leq 2,147,483,647$.

Ejemplos:

$10 \Rightarrow 1$

$25 \Rightarrow 2$

$3 \Rightarrow 0$

$0 \Rightarrow 1$

$1 \Rightarrow 1$

En respuesta a mi pregunta original sobre la optimización del este de F#, recibí la siguiente respuesta que yo soy incapaz de confirmar resuelve el problema dado correctamente.

Fuente: respuesta de StackOverflow por Alexandre C.

De nuevo, el número de soluciones entero de $x^2 + y^2 = k$ es de cuatro veces el número de primos divisores de $k$ que son iguales a $1 \bmod 4$.

Sabiendo esto, escribir un programa que da el número de soluciones es fácil: calcular los números primos hasta el $46341$ una vez y para todos.

Dado $k$, calcular el primer divisores de $k$ mediante el uso de la lista de arriba (la prueba de $\sqrt{k}$). El recuento de los que son igual a $1 \bmod 4$, y la suma. Multiplicar respuesta $4$.

Cuando voy a través de este algoritmo para $25$, I se $8$ lo cual no es correcto.

1. Para cada primer factor (pf) de $25$ (5,5 son los principales factores de $25%)
   • si pf % 4 = 1 (true 5), agregar 1 a contar
2. volver 4 * count (recuento sería de 2 aquí).

Así, por $25$, este sería de 8

Answer 1

Este es elaborado en detalle en muchos de introducción de libros de texto sobre la Teoría de números. Aquí está un resumen del tratamiento en Una Introducción a la Teoría de los Números (5ª Edición) por Iván Niven, Herbert S. Zuckerman, y Hugh L. Montgomery (Wiley, 1991, sección 3.6).

Teorema (Fermat) Deje $n$ ser un entero positivo, y escribir $n$ en forma $$n = 2^{\alpha}\prod_{p\equiv 1\pmod{4}} p^{\beta} \prod_{q\equiv 3 \pmod{4}} q^{\gamma}.$$ con $p$ $q$ números primos. A continuación, $n$ puede ser expresada como una suma de dos cuadrados si y sólo si todos los exponentes $\gamma$ son incluso.

Ahora, defina lo siguiente:

• $R(n)$: el número de pares ordenados $(x,y)$ de los números enteros tales que a $x^2+y^2=n$.
• $r(n)$: el número de pares ordenados $(x,y)$ tal que $\gcd(x,y)=1$ $x^2+y^2=n$ (llamados "adecuada representación de $n$");
• $P(n)$: el número de representaciones de $n$ por la forma $x^2+y^2$ con $\gcd(x,y)=1$, $x\gt 0$ y $y\geq 0$;
• $N(n)$: el número de soluciones de la congruencia $s^2\equiv -1\pmod{n}$.

Teorema. Un entero positivo $n$ está adecuadamente representado por la forma $x^2+y^2$ si y sólo si $-4$ es un cuadrado modulo $4n$.

En particular, desde la $-4$ es un cuadrado modulo $8$, pero no el modulo $16$, $n$ puede ser divisible por $2$, pero no por $4$. Si $p$ es una extraña flor de la forma$4k+1$, $-4$ es un cuadrado modulo $p$, y por Hensel del Lema se levanta a una solución modulo $p^k$ un y $k$; por lo $n$ puede ser divisible por poderes arbitrarios de los números primos de la forma $4k+1$. Por otro lado, si $p$ es un primo que divide a $n$ y es congruente a $3$ modulo $4$, $-4$ no es un cuadrado modulo $p$. Así, obtenemos:

Teorema. Un entero positivo $n$ está correctamente representables como suma de dos cuadrados si y sólo si los factores primos de a $n$ son todos de la forma $4k+1$, excepto para el primer $2$ que puede ocurrir en la mayoría de la primera potencia.

Ahora supongamos que $n$ es positiva y $n=x^2+y^2$ es una representación arbitraria. Set $g=\gcd(x,y)$; a continuación,$g^2|n$, por lo que $n = g^2m$, $\gcd(\frac{x}{g},\frac{y}{g}) = 1$, por lo $m$ está adecuadamente representada como la suma de los cuadrados de $\frac{x}{g}$$\frac{y}{g}$. Tenga en cuenta que $g$ pueden tener factores primos congruentes a $3$ modulo $4$, en los que se divide $n$ a un poder, y el poder de la $2$ que divide $n$ puede ser arbitraria así.

Teorema. Supongamos que $n\gt 0$. Entonces $P(n)=N(n)$, $r(n) = 4N(n)$ y $R(n)=\sum r\left(\frac{n}{d^2}\right)$, donde la suma se toma sobre todos los positivos $d$ tal que $d^2|n$.

Teorema. Deje $n$ ser un entero positivo y escribir $$ n = 2^{\alpha}\prod_{p}p^{\beta}\prod_q q^{\gamma}$$ donde $p$ ejecuta a través de primos divisores de $n$ congruente a $1$ modulo $4$ en el primer producto, y $q$ ejecuta a través de primos divisores de $n$ de la forma $4k+3$ en el segundo. Si $\alpha=0$ o $1$, y todos los $\gamma$$0$, $r(n) = 2^{t+2}$ donde $t$ es el número de números primos $p$ de la forma $4k+1$ que dividen $n$ (contadas con multiplicidad); de lo contrario, $r(n)=0$. Si todos los $\gamma$ son incluso, a continuación,$R(n) = 4\prod_p(\beta+1)$. De lo contrario, $R(n)=0$.

Answer 2

$25$ tiene dos primos divisores: $5$$5$, y tenemos que contar con ellos tanto porque ambas son congruentes a $1$ modulo $4$. Ahora multiplique por $4$. Ha $8$.

Esto cuenta las descomposiciones $$\begin{array}{cc} 3^2+4^2,& 3^2+(-4)^2, \\ (-3)^2+4^2, & (-3)^2+(-4)^2, \\ 4^2+3^2, & 4^2+(-3)^2, \\ (-4)^2+3^2, & (-4)^2+(-3)^2 \end{array} $$

Como se puede ver, multiplicando por $4$ al final se hace para atender a los signos: si usted está interesado sólo en "positivo" de la descomposición, entonces no lo hagas. Además, esta cuenta $a^2+b^2$ como diferente de $b^2+a^2$. Si no quieres que, además, tiene que restar el número de $N$ de descomposición de la forma $a^2+a^2$ (lo cual es fácil de calcular,...), divida por $2$, y, a continuación, agregue $N$.

Por último, si quieres saber por qué esto funciona, bien, hay muy pocas cosas mejores que consultar una introducción a la teoría de los números!

Answer 3

Una sencilla manera de ver esto sería considerar la factorización de $\displaystyle n$ en los Enteros de Gauss: $\displaystyle \mathbb{Z}[i] = \{a + bi \ \ | \ a \in \mathbb{Z}, \ b \in \mathbb{Z}\}$.

Es bien sabido que el que

• Los enteros de gauss única factorización de la propiedad (hasta unidades de $\displaystyle \pm 1, \pm i$).
• Los números primos (de $\displaystyle \mathbb{Z}$) de la forma $\displaystyle 4k+3$ son también primos en $\displaystyle \mathbb{Z}[i]$.
• Los números primos (de $\displaystyle \mathbb{Z}$) de la forma $\displaystyle 4k+1$ factorizar en $\displaystyle w w'$ primer $\displaystyle w$ ( $\displaystyle \mathbb{Z}[i]$ ) y $\displaystyle w'$ es el conjugado de a $\displaystyle w$. De hecho, si $\displaystyle w = a+ib$, entonces el primer es de la forma $\displaystyle a^2 + b^2$.
• $\displaystyle 2 = (1+i)(1-i)$ $\displaystyle 1+i$ es primo.

Ahora si $\displaystyle n = x^2 + y^2$$\displaystyle n = (x+iy)(x-iy)$, que corresponde a la factorización de $\displaystyle n$$\displaystyle \mathbb{Z}[i]$, que se puede obtener desde el primer factorización de $\displaystyle n$ $\mathbb{Z}[i]$ por elegir un subconjunto de los números primos de multiplicar, para obtener el $\displaystyle x + iy$. Los conjugados de los números primos ir hacia la $\displaystyle x-iy$. El resto necesita ser un cuadrado perfecto para distribuir una vez cada a $\displaystyle x+iy$$\displaystyle x-iy$. Nótese que esto implica que los números primos de la forma $\displaystyle 4k+3$ (que también son números primos en $\displaystyle \mathbb{Z}[i]$) necesidad de contar con un poder en la factorización.

Así que básicamente equivale a la búsqueda de las diferentes factorizations de los cuadrados perfectos que son factores de $\displaystyle n$ (después de ignorar los números primos de la forma $\displaystyle 4k+3$).

Nota: las unidades en las que se da el múltiplo de la $4$, si recuento $(x,y), (y,x), (-x,y),(y,-x)$.

(Por supuesto, esto no es una prueba formal...)

La esperanza de la ayuda.

Answer 4

Para un completamente inequívoca contraejemplo, considere la posibilidad de $k=15$: tiene un factor primo (5) que es congruente con 1 modulo 4, pero no puede ser escrito como suma de dos cuadrados. La razón (como se menciona en Morón y Arturo respuestas), es que un número no puede ser escrito como suma de dos cuadrados, a menos que todos sus factores primos que son congruente con 3 módulo 4 se planteó incluso poderes.