Ruby: primos y un primo
Siempre dicen que no hay mal que por bien no venga.
Anoche se publicaba el cuarto (y parece ser que último) problema del Google Treasure Hunt 2008 (el cuarto aún está en “competición”, pero se pueden realizar los otros tres anteriores), a eso de la 1.15 de la madrugada por estos lares… y ahí estaba yo (medio dormido, medio despierto) intentando solucionar el dichoso problema. Con lo sencillo que había sido el tercero, si estaba recargando la página cerca de la hora tenía oportunidades de ser el primero en solucionarlo.
Desgraciadamente, cuando me pusieron el problema delante, me dije a mi mismo que “primero ni de coña”. Y eso a pesar de que la solución naïve parece haber sido la más rápida. Pero no voy a poner aquí la solución, aunque puedo ofrecer herramientas para conseguirlo (y explicar mi error).
Ruby dispone de una clase Prime (require 'mathn') como parte de su librería estándar, aunque para desgracia de sus usuarios viene en el mismo archivo que el módulo Rational, que modifica el comportamiento de los enteros de una forma no siempre deseable.
Para realizar algunos problemas de Project Euler (que tengo un poco abandonado) era deseable tener disponible la clase que genere primos y no me tocase el funcionamiento “normal” de los enteros. Por eso la extraje a su propio archivo el código de la clase Prime (con algunos métodos matemáticos más, como un factorial y un binomial eficientes). Sin embargo el código de Prime en las versiones 1.8.x de Ruby es muy poco eficiente, pero por suerte en la versión 1.9 se le ha realizado una limpieza de cara (aunque extrañamente no ha sido backporteado a la reciente 1.8.7).
Sin embargo a la clase Prime de Ruby (incluso a la versión 1.9) le falta un método importante: prime?, para conocer si un número dado es primo o no. Después de buscar un poco encontré que el método comprobación de la de Miller-Rabin es un buen algoritmo para comprobar si un número es primo o no (además parece bastante eficiente). La única pega es que el método devuelve si el número es “probablemente primo” y que puede proporcionar falsos positivos, aunque si entiendo bien de las explicaciones de la página de MathWorld los resultados son correctos hasta números alrededor del 3,4×1014 (lo que no está nada mal). De cualquier forma se puede modificar la probabilidad cuando se invoca al método, aunque pasar de t = 7 parece no tener beneficios evidentes.
Podéis descargar el código de primes.rb.
Y ahora mi error (realmente estúpido), que ha hecho que en vez de llegar a la solución anoche, llegase esta mañana.
La idea que necesitáis conocer es que llevaba cuenta de unos índices de final y de comienzo, que determinaban que primos participaban en la suma. Estos índices iban aumentando de uno en uno, haciendo que una “ventana” se moviese sobre los primos conocidos. Cuando tocaba avanzar la ventana, la idea era que se eliminaba el primer primo y se incluía el siguiente.
Encontrad las “siete” diferencias:
p = Prime.new
# ...
# Versión incorrecta
suma += Prime.primes[final] - Prime.primes[inicio]
inicio += 1
final += 1
p.succ while Prime.primes.length < final+1
# Versión correcta
final += 1
p.succ while Prime.primes.length < final+1
suma += Prime.primes[final] - Prime.primes[inicio]
inicio += 1
