jueves, 22 de septiembre de 2016

Expresión cuadrática X^2+kY^2 = N


Hace unos meses publiqué en Twiter, como una curiosidad, esta tabla de desarrollos para el número 4516



No existen muchos números que admitan esas diez expresiones cuadráticas con enteros. En concreto estos son los primeros:

1009, 1129, 1201, 1801, 2521, 2689, 3049, 3361, 3529, 3889, 4036, 4201, 4516, 4561, 4729, 4804, 5209, 5569, 5881, 6841, 7204, 7561, 7681, 8089, 8521, 8689, 8761, 8929, 9081, 9241, 9601, 9769,…

¿Qué hay detrás de esta lista?

Realmente, el problema radica en resolver la ecuación X2+kY2=N, con k>0 buscando soluciones enteras X>1 Y>1, para evitar trivialidades.

Despejando X en X2+kY2=N nos queda

Por tanto, para averiguar si un número se puede desarrollar de esta forma, bastará recorrer los valores de Y entre 1 y la raíz cuadrada de N/k. El valor que dé como resultado un cuadrado en el radicando será válido.

Por ejemplo, hemos afirmado arriba que 4516 se puede desarrollar como X2+9Y2, con X>1 e Y>1. Según lo anterior, buscamos la raíz cuadrada de 4516/9, que resulta ser 22 (si tuviera decimales, truncaríamos). Por tanto habrá que ir probando desde Y=1 hasta Y=22 para ver qué valor da un cuadrado perfecto. Si se posee la función ESCUAD (puedes copiarla desde nuestra entrada http://hojaynumeros.blogspot.com.es/2015/02/numeros-especiales-que-son-un-producto.html ) para ver si un número es cuadrado perfecto, lo podemos organizar en una hoja de cálculo.



No hemos encontrado una solución hasta el valor 18, que junto a la raíz cuadrada de 1600 forma la expresión vista en el primer párrafo 40^2+9*18^2=4516

Función esforma(N;k)

Esta búsqueda que hemos efectuado se podría automatizar. Dado un número N y un coeficiente k podemos diseñar una función que devuelva TRUE si es posible la expresión N=X2+KY2 y FALSE en caso contrario. Existe una variante más útil, y es que si la expresión es posible, la devuelva en forma de String, y en caso contrario la frase “NO”.

En el Basic de VBA podría tener este código (añadimos la función ESCUAD por si no la has encontrado)

Public Function escuad(n) As Boolean
If n < 0 Then
escuad = False
Else
If n = Int(Sqr(n)) ^ 2 Then escuad = True Else escuad = False
End If
End Function

Public Function esforma(n, k) As String
Dim a, b, i
Dim es As Boolean
If k <= 0 Then esforma = "NO": Exit Function ‘Para k<=0 no hay solución
a = Int(Sqr(n / k)) ‘Tope de búsqueda
es = False
i = 1
While i <= a And Not es
b = n - k * i * i
If escuad(b) And b > 0 Then es = True: b = Sqr(b) ‘Se encuentra una solución
i = i + 1
Wend
If es Then
esforma = Str$(b) + "^2+" + Str$(k) + "*" + Str$(i - 1) + "^2" ‘Construcción del String
Else
esforma = "NO" ‘No es expresable
End If
End Function

Con esta función podemos construir un esquema para ver si un número admite la expresión N=X2+kY2 con un valor de k dado. En esta imagen encontramos el desarrollo de 4516 con coeficiente 5:



Hay que advertir que la función ESFORMA sólo da la primera solución posible, sin descartar que existan otras.

En esta otra imagen se comprueba que el número 1298 no admite la expresión N=X2+7Y2,


Ordenando un poco los cálculos podemos reproducir la imagen con la que comenzamos la entrada (con formato de hoja de cálculo)



En el caso de k=3 nos devuelve una solución distinta, ya que hay más de una, y hemos prolongado la tabla para comprobar que para los valores k=11 y k=13 no existe solución.

Listado de números expresables

Con esta función y un bloque FOR-NEXT podemos encontrar la lista de los primeros números que se pueden expresar como N=X2+kY para un valor de k determinado, e incluso con un doble bucle, los que son expresables para varios valores. Así hemos construido la lista de los que son expresables para los valores k=1..10: 1009, 1129, 1201, 1801, 2521, 2689,…

Números que se puedan expresar con los valores de k=1..11 existen muchos menos. Los primeros son: 7561, 10756, 14116, 14281,…

El número 21961 satisface las expresiones para k=1..13 y los números 32356, 35044 y 35281 llegan al valor 14. Llegan hasta el 15 los números 32356, 35044 y 35281. Y así podríamos seguir, con valores cada vez más altos y escasos.

En estos listados están incluidos valores de k que pueden resultar redundantes. Por ejemplo, si un número es expresable como X^2+8Y^2, también lo es como X^2+2(2Y)^2. Así que si comprobamos la expresión X^2+8Y^2 lo estamos haciendo también con X^2+2Y^2. Como los cálculos no eran muy lentos, hemos preferido dejarlos. En otros trabajos similares se suelen estudiar tan solo los valores primos de k.

Aspecto modular

Si nos fijamos en los restos módulo k, es fácil ver que para que N=X2+kY2,  ha de ser N congruente con X2  módulo k, es decir, que N ha de ser un resto cuadrático módulo k. Si se dispone de un listado de esos restos, o un programa que los genere, podemos averiguar para qué polinomios del tipo dado es expresable un número. La hoja que hemos alojado en esta dirección

http://www.hojamat.es/sindecimales/congruencias/herramientas/hoja/congruencias2.xlsm

contiene restos cuadráticos para cada caso

Hemos adaptado provisionalmente esta herramienta para este caso particular. A cada número que probemos le calculamos el resto respecto a k y lo comparamos con la lista de cuadráticos. Esta prueba sólo la efectuaremos para valores de k que sean primos impares. Los demás casos se reducen a este. Vemos unos ejemplos mediante imágenes:



Aquí vemos que el resto 5 no figura en el listado de restos cuadráticos (columna de la izquierda), 1, 4, 6, 9, 10,…módulo 13, por lo que no es expresable para ese coeficiente.



El mismo resultado obtendríamos mediante ESFORMA(4516,13).

Por el contrario, el número 35281 sí es expresable mediante X2+13Y2, , ya que su resto respecto al 13 es 12, y ese valor sí figura como resto cuadrático (el último de la primera columna). Lo dejamos aquí por si te apetece profundizar en la teoría de los restos cuadráticos.