2

Mi pregunta esta relacionada con el teorema de los cuatro cuadrados de Lagrange

Necesito una función (o una biblioteca), en el lenguaje Javascript o lenguaje parecido, que dado un numero entero positivo devuelva un arreglo con la suma de cuatro cuadrados.

Por ejemplo: para el número 61771 la factorización sería 61771 = 191² + 159² + 3² y lo que tiene que devolver (en notación json) seria [191, 159, 3]

Lo he intentado hacer. Pero el unico algoritmo que se me ocurre da como resultado 61771 = 248² + 16² + 3² + 1² + 1² lo cual es incorrecto.

Esto es lo que tengo:

function fn(n) {
  var x = Math.floor(Math.sqrt(n));
  var y = Math.pow(x, 2);
  var f = [];
  while (n > 0) {
    f.push(x);
    n -= y;
    x = Math.floor(Math.sqrt(n));
    y = Math.pow(x, 2);
  }
  return f;
}

Agradeceria que me explicaran.

Saludos!

2

1 respuesta 1

2

Si definimos que

  • el algoritmo converge cuando la función retorna 4 o menos elementos
  • no converge cuando retorna más de 4 elementos
  • la semilla es el primer elemento que insertamos en el array

Podemos decir que al asumir que la semilla es el máximo cuadrado perfecto menor a N, el algoritmo en algunos casos no converge.

En ese caso, 61771 tiene como mayor cuadrado perfecto 248², pero el algoritmo no converge con esa semilla.

Si probamos con la semilla 248 no converge (248² + 16² + 3² + 1² +1²)

Si probamos con la semilla 247 no converge (247² + 27² + 5² + 2² +2²)

Si probamos con la semilla 246 no converge (246² + 35² + 5² + 2² +1²)

Y finalmente, con la semilla 245 SI CONVERGE: 245² + 41² + 8² + 1²

Mi solución, bastante a lo bruto, sería ir probando semillas, y si no converge probar de nuevo restando 1 a la semilla, hasta que converja.

function fn(n,delta) {
  var n0 = n;
  var x0 = Math.floor(Math.sqrt(n))-delta;
  var y0 = Math.pow(x0, 2);
  var f = [];
  n -= y0;
  f.push(x0+'²');
  while (n > 0) {
    
    var x1 = Math.floor(Math.sqrt(n));
    var y1 = Math.pow(x1, 2);
    n -= y1;
    f.push(x1+'²');
  }
  if(f.length>4) {
    return fn(n0,delta+1);
  }
  var respuesta={numero_inicial: n0, iteraciones:delta, numeros:f.join(' + ')};
  return respuesta;
}

var numero = Math.floor(100000*Math.random());
console.log(fn(numero,0));

¿Por qué es "a lo bruto"? Bueno, es porque en algunos casos se cumple que el número puede descomponerse en 3 cuadrados perfectos, usando una semilla aún menor que la que devuelve mi algoritmo, siempre y cuando N no tenga la forma 4^a (8 m + 7) donde a y m son enteros. Pero ese es el llamado Teorema de los 3 cuadrados de Legendre que después demostró Gauss, y no tengo intención de ahondar tanto cuando tu pregunta se responde con 4 elementos.

2
  • como curiosidad: podría darse el caso de que no convergiera en ningún caso entre 1 y sqrt(num) ? De estos temas no tengo ni idea, solo es por si hubiera que indicar en tu algoritmo una salida del tipo "no converge".
    – Jakala
    el 12 sep. 2018 a las 12:06
  • Bueno, se podría poner la condición de que el segundo elemento del arreglo no pueda ser mayor a la semilla porque en ese caso estaríamos de vuelta en la iteración anterior. Pero el teorema de los cuatro cuadrados tiene una demostración basada en cuatro lemas que a su vez tienen su respectiva demostración. No me acuerdo de esa demostración porque la tuve que aprender a mediados de 1995 en Cálculo I, y de eso como verás ha pasado demasiado tiempo. Podría copiar y pegar una demostración de otra página, pero sería trampa.
    – ffflabs
    el 12 sep. 2018 a las 12:50

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.