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í.
