Descubrí en http://oeis.org/A094552 que 18921 separa dos sumas de cuadrados con idéntico total, una hasta él y otra a partir de él, sin incluirlo (también podría contarse con él). Después de investigarlo, llegué a esta comprobación:
suma(i=10472,18920,i^2)=1875012353984
suma(i=18922,23145,i^2)=1875012353984
Aquí, más que la sucesión resultante con los números
que cumplen esta condición, que ya está publicada en la dirección referida, nos
interesarán los algoritmos que se puedan usar en este caso y en otros afines.
Los primeros números publicados son:
52, 100, 137, 513, 565, 1247, 8195, 13041, 18921,
35344, 40223, 65918, 68906, 121759, 132720, 213831, 215221, 235469, 265654,
506049, 520654, 585046, 598337, 817454, 993142, 1339560, 1579353, 2331619,
2843086, 3594812…
Nuestro objetivo será, además, encontrar las dos sumas
con igual total a las que el número separa. Para ello habrá que identificar previamente
(y ese será el objetivo prioritario) los límites de esas dos sumas a partir de
su inicio en n-1 y n+1 respectivamente. El problema será la lentitud del
proceso, pues requiere dos bucles anidados para crear las sumas, y eso, en
números de más de tres cifras, puede ser resultar poco eficiente en equipos
pequeños. Por ello, plantearemos tres algoritmos, el primero el “ingenuo”, el
que inicialmente nos viene a la mente, el segundo con el uso de técnicas
algebraicas, y el tercero con acumulación progresiva de cada suma.
Primer algoritmo (ingenuo)
Hemos creado la función frontera0, para que, dado
un número cualquiera, determine si cumple la propiedad o no y cuáles son los
extremos de las dos sumas con igual total. Devolverá un “NO” o bien esos
extremos.
La idea es ir sumando cuadrados a la derecha del
número N. Terminaremos la búsqueda al llegar a 2N, porque la otra suma sólo
podrá tener N sumandos (si no, invadiría el cero y los negativos) y la suma
superior tendrá menos sumandos que la inferior (porque estos son mayores).
Una vez determinada una suma provisional, recorreremos
el rango 1…N-1 en orden inverso (lo esperable es que no llegue al 1) y para
cada suma inferior compararemos con la superior para ver si son iguales, en
cuyo caso sí hay solución. Si no, seguimos añadiendo sumandos a ambas.
Listado
de la función para Excel y Calc
Function frontera0(n)
Dim j, k, s, t, s1, p, q
Dim b$
t = 0 ‘Indicador
de que hay solución. En principio t=0 porque no la hay.
s = 0 ‘Suma
superior
j = n + 1 ‘Comienza
en N+1
While t = 0 And j < 2 * n ‘No
llega a 2N
s = s + j ^ 2 ‘Se
suman los cuadrados
k = 1 ‘Se
inicia la búsqueda de la suma inferior
s1 = 0 ‘Contiene
la suma inferior
While t = 0 And k < n
s1 = s1 + (n - k) ^ 2 ‘Acumula
la suma inferior en orden inverso
If s1 = s Then ‘Si
ambas sumas son iguales, hay solución
t = 1 ‘Indicador
de solución
p = n - k: q = j ‘Se
recogen las soluciones
End If
k = k + 1
Wend
j = j + 1
Wend
If t = 0 Then frontera0 = "NO"
Else frontera0 = Str$(p) + Str$(q) ‘Devuelve “NO” o la solución
End Function
Si planteamos una búsqueda sistemática con esta función, obtenemos las primeras soluciones, que coinciden con las publicadas en OEIS, pero con el añadido de los límites de las sumas:
N Límites
52 7 65
100 55 122
137 22 172
513 169 642
565 330 687
1247 572 1545
Para probar que los límites son correctos se puede usar
cualquier calculadora avanzada. Hemos usado Wiris, que es gratuita y
muy clara en su aspecto. La probamos con la solución correspondiente al 137.
Calculamos la suma de cuadrados desde 22 hasta 136 y, por otra parte, desde 138
hasta 172. Nótese que la suma superior tendrá siempre menos sumandos que la
inferior.
De esta forma hemos comprobado que 137 es un término de la sucesión buscada.
Segundo
algoritmo, con ayuda del Álgebra
Nos basamos en la fórmula de los primeros cuadrados desde
1 hasta n:
Si se conoce la suma de cuadrados s0 desde 1 hasta n-1 (de fórmula (n-1)*n*(2n-1)/6) y el valor de la
suma superior s, restando s0-s equivaldrá a un k(k+1)(2*k+1)/6
para cierto valor de k. La ventaja es que ese valor se puede encontrar. Veamos
cómo.
Si llamamos M a la diferencia s0-s, tendremos:
Esto nos da una cota superior para el valor de k
De igual forma:
Es sencillo comprenderlo al comparar las dos fracciones.
Seguimos:
Por tanto, para cada suma superior podemos calcular la k
correspondiente en la suma inferior (esa k se corresponde con la suma desde 1 hasta
el tope inferior), quedándonos con la parte entera de esa raíz.
Este razonamiento evita el doble bucle, porque, para cada
suma superior obtendremos el límite correspondiente en la inferior. El
algoritmo quedaría según el listado de la segunda función de Excel, frontera1:
Function frontera1$(n)
Dim j, k, s, t, s1, s0, m, p, q
t = 0 ‘Indicador de solución
s = 0 ‘Suma
superior
j = n + 1 ’Primer
sumando
s0 = n * (n - 1) * (2 * n - 1) / 6 ‘Suma
en n-1
While t = 0 And s < s0
s = s + j ^ 2
m = s0 – s ‘Diferencia
entre sumas, para calcular k
k = Int((3 * m) ^ (1 / 3) + 0.000001) ‘Redondeamos
por defecto
s1 = s0 - k * (k + 1) * (2 * k + 1) / 6 ‘Suma
inferior calculada
If s1 = s Then t = 1: p = k + 1: q = j ‘Hay
solución
j = j + 1
Wend
If t = 0 Then frontera1 = "NO"
Else frontera1 = Str$(p) + Str$(q)
End Function
Tercer
algoritmo (paso a paso se marcha mejor)
En el tercer intento comenzaremos con los valores s=(n+1)^2 y s1=(n-1)^2. Es evidente que s1<s,
por lo que podemos ir añadiéndole sumandos hacia atrás a s1 hasta que sobrepase a s,
Si llegado a este punto las sumas son iguales, hemos terminado y, si no,
aumentamos alternativamente s y s1 hasta que se igualen o s1 llegue hasta el
tope 0, con lo que no existirá solución.
Esta sería la función para el algoritmo tercero:
Function frontera2$(n)
Dim j, k, t, s1, s0, m, p, q
t = 0 ‘Indicador
de solución
k = n – 1 ‘Índices
de las sumas
j = n + 1
s0 = k ^ 2 ‘Inicios
de las sumas
s1 = j ^ 2
While t = 0 And k > 0 ‘Bucle
de seguridad por si no hay solución
While s0 < s1 And k > 0 And t = 0
k = k - 1
s0 = s0 + k ^ 2 ‘Se
incrementa s0 si es menor que s1
Wend
While s0 > s1 And t = 0
j = j + 1
s1 = s1 + j ^ 22 ‘Se
incrementa s1 si es menor que s0
Wend
If s1 = s0 Then t = 1: p = k: q = j ‘Si
se igualan, hay solución
Wend
If t = 0 Then frontera2 = "NO"
Else frontera2 = Str$(p) + Str$(q)
End Function
Este será quizás el algoritmo más rápido (no lo he
cronometrado, pero se le ve con más velocidad). Es reconfortante comparar las
tres posibilidades y comprobar la unicidad de resultados:
Como se afirmó en los primeros párrafos, el interés de
este estudio residía en los algoritmos, y no en los resultados. En la siguiente
entrada aplicaremos estas ideas a otros tipos de números.
No hay comentarios:
Publicar un comentario