Necesito ayuda para entender la función de Suma de Cuadrados $r_2(n)$

Question

Estoy tratando de entender cómo encontrar rápidamente el número de dos cuadrados que se pueden sumar para formar un número 'n'. Este es mi referencia.

He escrito una función que creo que me da respuestas correctas, pero necesito que se ejecute más rápido. Básicamente lo que hace es recorrer los posibles números por debajo de la raíz cuadrada de n, y verifica si esos dos números al cuadrado son iguales a n. Luego sumo 4 al total, ya que incluye cuando algún número es negativo (positivo al cuadrado). Si entiendes Java, aquí está mi código:

static int SquaresR2(int n) {
    int sum = 0;
    outer:
    for(int a=0; ab) break outer;
                sum+=4;
                System.out.println(n+" = "+a+"^2 + "+b+"^2");
            }
        }
    }
    sum*=2;

    if(Math.sqrt(n)==(int)Math.sqrt(n)) sum+=4;
    return sum;
}

En Wolfram MathWorld dice que encontrar la Suma de Cuadrados k=2 se relaciona con factorizar n en $n=2^{a_{0}} p_{1}^{2_{a_{1}}} ... p_{r}^{2_{a_{r}}} q_{1}^{b_{1}} ... q_{s}^{b_{s}}$ donde los $p_{i}$s son primos de la forma 4k+3 y los $q_{i}$s son primos de la forma 4k+1. No tengo (casi) idea de lo que esto significa.

También habla sobre $B=(b_{1}+1)(b_{2}+1)...(b_{r}+1)$, de lo cual tampoco entiendo nada.

Estoy pensando que tiene algo que ver con factorizar n usando primos. Soy un estudiante de último año de secundaria que está llevando Cálculo 1.

¡Por favor, ayúdame! Gracias de antemano.

Answer 1

Dejaré de lado las preguntas de (a) si en realidad calcular la factorización prima de números es realista o práctico para este algoritmo o (b) por qué lo que MW ha hecho es cierto. En su lugar, me enfocaré en mostrar lo que MW está diciendo. Asumo que conoces acerca de números primos y factorizaciones primas.

Cada entero positivo tiene una factorización única en potencias de números primos. Por ejemplo,

$$60=2^2\cdot3^1\cdot5^1,\qquad 1225=5^2\cdot7^2,\qquad 7118280=2^3\cdot3^4\cdot5\cdot13^3.$$

Todos los números primos impares son o de la forma $4k+1$ o $4k+3$. Aquí hay una tabla para los primeros cuantos primos $p$:

$$\begin{array}{|r|l|} \hline p & 4(\circ)+\square \\ \hline 3 & 4(0)+\color{Blue}3 \\ 5 & 4(1)+\color{Red}1 \\ 7 & 4(1)+\color{Blue}3 \\ 11 & 4(2)+\color{Blue}3 \\ 13 & 4(3)+\color{Red}1 \\ 17 & 4(4)+\color{Red}1 \\ 19 & 4(4)+\color{Blue}3 \\ 23 & 4(5)+\color{Blue}3 \\ \hline \end{array}$$

Así que podemos tomar los primos en cualquier factorización en potencias de primos y categorizarlos como $\color{Green}2$ o de una de las formas $\color{Red}{4k+1}$ o $\color{Blue}{4k+3}$. Veamos los ejemplos anteriores nuevamente:

$$60=\color{Green}{2^2} \cdot \color{Blue}{3^1} \cdot \color{Red}{5^1},\qquad 1225=\color{Red}{5^2} \cdot \color{Blue}{7^2},\qquad 7118280=\color{Green}{2^3} \cdot \color{Blue}{3^4} \cdot \color{Red}{5} \cdot \color{Red}{13^3}.$$

Lo que MW dice ahora es

• La potencia de $2$ en la factorización prima de $n$ no afecta el valor de $r_2(n)$.
• Si alguna potencia de un primo azul ($4k+3$) en la factorización de $n$ es impar, por ejemplo $3^1$ en $60$, entonces $r_2(n)=0$.
• De lo contrario, sin ningún orden en particular, sea $b_1, b_2, b_3, \dots$ las potencias de los primos rojos ($4k+1$) en la factorización de $n$. Entonces tenemos la igualdad $r_2(n)=4(b_1+1)(b_2+1)\cdots$.

¿Puedes usar estos hechos y los ejemplos dados para calcular $r_2(60)$, $r_2(1225)$ y $r_2(7118280)$?

Answer 2

No estoy seguro acerca de la rapidez (tendrás que hacer tus propias pruebas), pero aquí tienes un método que podrías considerar, basado en esta línea en la OEIS:

transformación de Euler de la secuencia periódica $4,-6,4,-2,\dots$ - Michael Somos, 19 jul 2004

Más concretamente, considera la función

$$a_n=\begin{cases}4&\text{si }n\text{ es impar}\\-2&\text{si }n\bmod 4=0\\-6&\text{si }n\bmod 4=2\\\end{cases}$$

y forma la función

$$c_n=\sum_{d\mid n} d a_d$$

donde $\sum\limits_{d\mid n}$ significa que se debe sumar sobre todos los enteros $d$ que son divisores de $n$.

Luego podemos calcular $r_2(n)$ a través de la relación de recursión

$$r_2(n)=\frac1{n}\left(c_n+\sum_{j=1}^{n-1} c_j\; r_2(n-j)\right)$$

con la condición inicial $r_2(1)=4$.

Implementar $a_n$ en código debería ser sencillo; implementar $c_n$ solo requeriría verificar los divisores de $n$ y sumar los términos correspondientes; implementar la función real de suma de dos cuadrados $r_2(n)$ requerirá almacenamiento en caché y cualquier otro truco necesario para la recursión.

---

Aquí tienes una implementación de ejemplo en Mathematica:

c[k_Integer] := DivisorSum[k, # Piecewise[{{4, OddQ[#]},
                                           {-6, Mod[#, 4] == 2},
                                           {-2, Mod[#, 4] == 0}}] &];

r2[1] = 4;
r2[k_Integer] := r2[k] = (c[k] + Sum[c[j]*r2[k - j], {j, 1, k - 1}])/k

Comprueba los primeros cincuenta enteros positivos:

Apply[And, Thread[(b /@ Range[50]) - SquaresR[2, Range[50]] == 0]]
True