Otra entrada migrada de la vieja web:
Visitando la página de
ProjectEuler.Net escogí intentar resolver
el problema 108, el cual dice:
Hay que hallar el mínimo
valor de n para el que existen al menos 1000 soluciones a la ecuación 1/x + 1/y
= 1/n, donde "x", "y", "n" son números naturales.
Parecía que la solución
estaba en simplemente meter x e y en dos bucles anidados y evaluar la ecuación
para distintos valores de "n" y, junto con un contador, romper los bucles cuando
éste exceda mil. Mas el primer problema que hallé es cómo encontrar los límites
superiores de los bucles ¿cómo sé que no debo buscar en la infinita totalidad
del conjunto de números naturales? En el problema se entiende que la solución
existe y es finita.
Después de jugar con la
ecuación, despejar variables, quitar denominadores, iguala a cero... y
finalmente frustrarme, un foro me dio una pista: la solución de los límites para
"x" e "y" está en la ecuación en su forma original.
Entonces me puse a
analizarla y a meditarla...
Entonces (si se ignoran
todos los dibujitos) salta a la vista
que "x" e "y" deben ser mayores que "n" para cumplir la condición que todas las
variables son números naturales. El valor de n+1 es el límite inferior de los
bucles.
Si hago x = n+1:
Si el valor mínimo de "x" e
"y"
es n+1, el valor máximo será n^2+n, ya que para cumplir que 1/x + 1/y = 1/n, si
"x" tiene un valor máximo, "y" tendrá un valor mínimo. En una fracción, mientras más
grande es el denominador, más pequeña será la fracción, y viceversa.
Mi primer intento de
resolver el problema 108 tenía dos bucles anidados que evaluaban los valores de
"x" e "y", dentro de un bucle while, el cual se rompía cuando un contador superaba
el valor de 1000, mientras no lo hiciera incrementaba el valor de "n". Mirando la
ecuación también se deduce que "n" debe ser mayor a 32, ya que n^2+n - (n+1) =
31.606, redondeando: 32.
Pero este primer intento
era mortalmente lento.
Luego de correr el
programita para valores pequeños de "n", noté que las soluciones se repetían
cuando "x" e "y" eran iguales a 2*n. Esto se entiende por la propiedad
conmutativa de la suma:
El siguiente valor entero es
2n + 1, donde "z" puede ser "x" ó "y", pues los valores se repiten para las dos
variables:
Se concluye que se puede
decir que "x" va desde n+1 hasta 2n, "y" va desde 2*n+1 hasta n^2+n.
Para que se cumpla la
condición de las mil soluciones, "x" debe tener al menos mil valores, es decir:
2n - (n+1) >1000. El valor mínimo para "n" es 999. En el programa empieza desde
1000:
Pero esta solución también
tardaba siglos.
Entonces, jugando un poco
con la ecuación, llegué a esto:
Para el problema 108, no
interesan los valores de "n", "x" e "y", sólo si la relación xy/(x+y) da mil
soluciones enteras. Evalúo los posibles valores de "x" e "y" para el intervalo
[n+1, 2n], dentro de dos bucles:
Queda mucho mejor y da la
solución al problema en menos de un minuto, corriendo como código administrado
sobre .Net 3.5 :D
Mi programita se veía
interesante y bonito... tan bonito que me dije ¿por qué no pasarlo a Linq?
Dado que el compilador debe
hacer varias conversiones si se usa Linq, esta última solución es unas tres
veces más lenta.
El código fuente puee descargarse de aquí.