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
    Commented el 12 sept. 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
    Commented el 12 sept. 2018 a las 12:50

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

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