jueves, 19 de enero de 2017

Número de descomposiciones en diferencia de cuadrados


Después de jugar bastante con los números naturales, he observado la disparidad existente entre ellos respecto al número de sus descomposiciones en diferencias de cuadrados. Nos referimos al número de soluciones de

N=a^2-b^2 con a y b enteros y a>0 y b>=0 para un N dado.

Hay números que no admiten ninguna descomposición de este tipo, como el 22, y otros que admiten muchas. Un ejemplo es el 1680, que admite doce:

1680=421^2-419^2=212^2-208^2=143^2-137^2=109^2-101^2=89^2-79^2=
=76^2-64^2=67^2-53^2=52^2-32^2=47^2-23^2=44^2-16^2=43^2-13^2=41^2-1^2

En la tabla lo puedes comprobar:



¿De qué depende esto? Lo iremos viendo más adelante.

Obtención del número de descomposiciones

Al igual que hemos procedido con otros temas, comenzaremos encontrando las soluciones sin apoyo de la teoría, para más adelante fundamentarlo y después extraer propiedades y curiosidades.

Cualquier algoritmo para resolver esta cuestión se puede basar en el hecho de que una descomposición de este tipo equivale a expresar N mediante un producto de factores con la misma paridad, ambos pares o ambos impares. En efecto, si N=b^2-a^2 resultaría N=(a+b)(a-b), y ambos factores tienen la misma paridad, como se comprueba estudiando los cuatro casos posibles para a y b: par-par, par-impar, impar-par e impar-impar. Es fácil. A la inversa: si N=m*n, ambos de la misma paridad resultaría que (m+n)/2 y (m-n)/2 serían enteros, cumpliéndose que N=((m+n)/2)^2-((m-n)/2)^2

El número de descomposiciones de N en diferencia de cuadrados coincide con el de productos con factores de la misma paridad y resultado N.

Para hacer más fáciles los trabajos, admitiremos que b pueda ser nulo, o de forma equivalente, que los dos factores sean iguales.

Establecida esta propiedad, la búsqueda se efectuaría encontrando divisores d de N tales que d y N/d tengan la misma paridad. Esto lo podemos lograr fácilmente, usando divisiones enteras y aritmética modular. En el siguiente ejemplo lo implementamos como función Basic para hojas de cálculo:

Public Function numdifcuad(n)
Dim i, m
m = 0 ‘Contador de casos
For i = 1 To Sqr(n) ‘Se llega a la raíz cuadrada para evitar repeticiones de divisores
If n / i = n \ i Then ‘Si el cociente es igual al cociente entero, es que es divisor
If Abs(i - n / i) Mod 2 = 0 Then m = m + 1 ‘el divisor i y el cociente n/i tienen la misma paridad, porque su diferencia da resto 0 módulo 2, luego incrementamos el contador.
End If
Next i
numdifcuad = m
End Function

Así de sencillo. Con esta función podemos contar las descomposiciones posibles para cada número. En la tabla puedes observar las correspondientes a los primeros números:



Verás que se dan muchos casos, desde el 22 o el 14, que no admiten descomposiciones, hasta el 16 o el 15, que admiten 2. Si siguiéramos leyendo hacia abajo descubriríamos que 45 es el primero que admite 3 casos: 45=23^2-22^2=9^2-6^2=7^2-2^2.que se corresponden con las descomposiciones en producto 45=45*1=15*3=9*5, todas con factores de igual paridad. El primero con cinco casos es el 96, y así podríamos seguir hasta 1680 que vimos presenta doce.



Estos resultados están ya publicados en https://oeis.org/A034178



Podemos comprobar que coinciden con nuestros resultados

Análisis teórico de la situación

Es importante distinguir en principio si N es par o impar.

Caso 1: N es impar

Si N es impar, todos los posibles pares de factores N=m*n tendrán la misma paridad, luego sólo tenemos que contarlos. Recordamos que la función TAU, que cuenta los divisores, viene dada por la fórmula


En ella a, b c,…representan los factores primos y p, q, r,…sus exponentes. Como los divisores han de formar pares, deberemos encontrar la mitad de la función (si esta es par), por tanto, si expresamos el número de descomposiciones mediante la función ND, tendremos:


Lo comprobamos. Según la tabla el 21 admite dos descomposiciones. Como 21=3*7, ?(21)=(1+1)(1+1)=4, y su mitad entera es dos, como indica la tabla.

Si TAU es impar, será porque todos los exponentes serán pares, con lo que N será un cuadrado, apareciendo entonces un par nuevo al multiplicar la raíz cuadrada por sí misma. Podemos unificar ambas situaciones:


El segundo paréntesis valdrá cero en el caso par y uno en el impar.

Es el caso del número 3969:



Los factores son todos impares, los exponentes, 4 y 2, pares. TAU valdrá en este caso (1+4)(1+2)=15. Su mitad entera es 7, y añadimos 1 por su raíz cuadrada. Coincide entonces con el valor 8 que nos da NUMDIFCUAD.

Caso 2: N es par

En este caso aparece el factor 2, lo que obliga a que los dos factores que buscamos sean ambos pares y deban contener el 2 como factor. Esto no es posible si el factor 2 es único, con exponente 1, y esa es la causa de que 6, 10, 14 o 22 no presenten descomposiciones.

No admiten descomposiciones en diferencias de cuadrados los múltiplos de 2 que no lo sean de 4, es decir, los del tipo 4k+2

N es potencia de 2

Siguiendo un razonamiento similar al caso impar, deberemos encontrar la función TAU. Como tratamos con un solo exponente, sea p, el número de divisores será 1+p, pero al ser el caso par, el divisor 1 no nos interesa, y nos quedarían tan solo p divisores. Así, para p=5 dispondríamos de 2, 4, 8, 16 y 32. La potencia completa, en este caso 32, no nos valdría, porque tendría que formar par con el 1, que es impar, luego sólo nos quedan p-1 divisores disponibles. Esto vuelve a confirmar que el caso p=1 no produce pares de la misma paridad.

Los pares engendrados por el 2 serán pues, (p-1)/2 si p es impar y Int((p-1)/2)+1 si es par, por el par que se gana por su raíz cuadrada. Unificando:

N no es potencia de 2

Si el número es potencia de 2, sin factores impares, esta expresión vale, pero, en caso contrario, estas posibilidades del factor 2 se deberán multiplicar por las correspondientes al factor impar. La complicación surge del hecho de cada par puede producir productos idénticos, que se contarían dos veces, y hay que tener en cuenta los pares de factores repetidos en el caso de que p sea par. Por ello, la única forma de encajar todo es:


Multiplicamos el número de pares con factores desiguales de la potencia de 2 contenida en N por todos los factores de la parte impar de N, y después, en otro producto, los factores con repetición se multiplican sólo por los pares que se forman en la parte impar. Algo complicado, pero funciona.

Hemos plasmado los tres casos en una única función, a la que llamaremos NUMDIFCUAD2:

Public Function numdifcuad2(n)
Dim p, q, r, s, t, m

m = n: p = 0
While m Mod 2 = 0: m = m / 2: p = p + 1: Wend ‘Extraemos la potencia de 2
If p = 1 Then numdifcuad2 = 0: Exit Function ‘Caso imposible
q = n / 2 ^ p ‘q es la parte impar
If q = 1 And p > 1 Then numdifcuad2 = Int((p - 1) / 2) + (p - 1) Mod 2
‘Es potencia de 2 pura
If p = 0 And q > 1 Then t = fsigma(q, 0): numdifcuad2 = Int(t / 2) + t Mod 2
‘Es un número impar
If p > 1 And q > 1 Then t = fsigma(q, 0): numdifcuad2 = t * Int((p - 1) / 2) + ((p - 1) Mod 2) * (Int(t / 2) + t Mod 2)
‘Tiene parte par y parte impar
End Function

La complejidad del cálculo nos ha aconsejado comprobar mediante tablas si las dos versiones de NUMDIFCUAD coinciden. Lo hemos probado desde 1 hasta 100000, sin que aparecieran discrepancias. Como ejemplo, adjuntamos los valores de algunos números de seis cifras entre los que hay impares, pares y una potencia de 2 pura:



Otra interpretación

Como todo cuadrado es suma de números impares consecutivos, como por ejemplo 16=1+3+5+7, al restar dos cuadrados se eliminarán sumandos impares, quedando tan sólo aquellos que no sean comunes. Es, por ejemplo, el caso de 44=12^2-10^2=21+23 o el de 72=9^2-3^2=7+9+11+13+15+17

Así que el número de descomposiciones que estamos estudiando coincide con el de formas de expresar el número como suma de impares.