Llevo dos días sin poder resolver el problema 51 de Project Euler, así que decidí intentar algún otro. Encontré el que muestro a continuación, que me pareció divertido y sencillo, el único detalle es que mi solución no es tan eficiente como pensé.
El motivo de esta entrada es desafiarte a resolverlo mejorando el análisis que yo hice (es decir, el tiempo que tardó mi programa si es que programarás en Python); no importa cómo lo resuelvas, lo importante es que la solución sea elegante, sencilla y rápida.
A continuación muestro el problema, mi resultado y tanto el análisis como el programa que hice para obtenerlo. Mi recomendación es que primero lo resuelvas a tu manera. Si te interesa resolver más problemas entra a project euler y lleva tu propio récord.
Mi respuesta:
Análisis y código fuente:
Comenzando desde 1, el número de la $i$-ésima esquina superior derecha de la espiral cuadrada, $k_i$ está dado por
$$k_i=k_{i-1}+8(i-1)+2\hspace{0.25in}\text{con}\hspace{0.25in}k_0=1$$ Para las 3 esquinas restantes (que etiqueto con 1, 2 y 3), en cada vuelta
\begin{align*}k_{(i,1)}&=k_i+2i\\
k_{(i,2)}&=k_i+4i\\
k_{(i,3)}&=k_i+6i\end{align*} Así entonces, generamos
\begin{align*}k_1&=k_0+2=1+2=3\\
k_{(1,1)}&=k_1+2(1)=3+2=5\\
k_{(1,2)}&=k_1+4(1)=3+4=7\\
k_{(1,3)}&=k_1+6(1)=3+6=9\end{align*} Falta revisar si los números son primos y contar. En el problema se menciona que en la diagonal inferior izquierda todos son cuadrados impares, así que éstos se pueden ignorar.
Mi código en Python se ve así:
Apenas me he enterado que la espiral utilizada se llama Espiral de Ulam, para el que esté interesado en conocer más. La espiral en general, por ejemplo, muestra la siguiente distribución de números primos:
El motivo de esta entrada es desafiarte a resolverlo mejorando el análisis que yo hice (es decir, el tiempo que tardó mi programa si es que programarás en Python); no importa cómo lo resuelvas, lo importante es que la solución sea elegante, sencilla y rápida.
A continuación muestro el problema, mi resultado y tanto el análisis como el programa que hice para obtenerlo. Mi recomendación es que primero lo resuelvas a tu manera. Si te interesa resolver más problemas entra a project euler y lleva tu propio récord.
Comenzando con 1 y rotando en sentido contrario a las agujas del reloj de la siguiente manera, se forma una espiral cuadrada con lados de longitud 7.37 36 35 34 33 32 31Es interesante que los cuadrados impares se sitúan en la diagonal inferior derecha, pero aún más interesante es que 8 de los 13 números de las dos diagonales son primos, es decir, una proporción de 8/13 ≈ 62%.
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
Si enrollamos una nueva capa en esta espiral, se formará una espiral cuadrada con lados de longitud 9. Si este proceso continúa, ¿cuál es la longitud del lado de la espiral cuadrada para la cual la relación de primos en diagonales es inferior al 10%?
Mi respuesta:
Side length of the square spiral: 26241
Time elapsed: 26.3150000572 seconds
Análisis y código fuente:
Comenzando desde 1, el número de la $i$-ésima esquina superior derecha de la espiral cuadrada, $k_i$ está dado por
$$k_i=k_{i-1}+8(i-1)+2\hspace{0.25in}\text{con}\hspace{0.25in}k_0=1$$ Para las 3 esquinas restantes (que etiqueto con 1, 2 y 3), en cada vuelta
\begin{align*}k_{(i,1)}&=k_i+2i\\
k_{(i,2)}&=k_i+4i\\
k_{(i,3)}&=k_i+6i\end{align*} Así entonces, generamos
\begin{align*}k_1&=k_0+2=1+2=3\\
k_{(1,1)}&=k_1+2(1)=3+2=5\\
k_{(1,2)}&=k_1+4(1)=3+4=7\\
k_{(1,3)}&=k_1+6(1)=3+6=9\end{align*} Falta revisar si los números son primos y contar. En el problema se menciona que en la diagonal inferior izquierda todos son cuadrados impares, así que éstos se pueden ignorar.
Mi código en Python se ve así:
from __future__ import division
import time
t0 = time.time()
def isprime(x, i=2):
while i <= (x/i):
if x%i == 0: return False
i += 1
return True
prime, total = 0, 1
k, n = 3, 2
while prime/total >= 0.1 or prime == 0:
for i in range(3):
if isprime(k+i*n) == True:
prime += 1
k = k + 4*n + 2
total += 4
n += 2
print 'Side length of the square spiral:',n-1
print 'Time elapsed:',time.time()-t0,'seconds'
Apenas me he enterado que la espiral utilizada se llama Espiral de Ulam, para el que esté interesado en conocer más. La espiral en general, por ejemplo, muestra la siguiente distribución de números primos:
