Me tomó como una semana resolver este problema, y aun así lo he hecho de una forma bastante grotesca pues no he tenido tiempo para estudiarlo o para entender formas más elegantes de resolverlo. He estado bastante ocupado con las actividades curriculares, por lo que no he trabajado más en ello, aunque al menos he aprendido un poco más el uso de Matlab e intentaré aprender también SciPy (de Python) para resolver problemas de análisis numérico.
El problema es el 26 de Project Euler y se puede resumir a: Encuentra el valor de d<1000 para el cual 1/d contiene el periodo más grande en su parte fraccionaria. Mi sorpresa ha sido que la solución se obtiene elegantemente con teoría de números y álgebra abstracta al resolver el algoritmo discreto ${10^k\equiv1\mod{n}}$. Sin embargo son herramientas de las cuales aún no tengo pleno conocimiento; como sea, quien esté interesado puede consultar esta liga.
Estuve bastante ansioso por resolver el problema, y finalmente lo hice, aunque fuera de forma rudimentaria, pero encontrando algunas cosillas interesantes.
Lo difícil fue determinar cuándo la parte fraccionaria decimal era periódica. Digamos que tenemos 0.3333… bueno, resulta muy sencillo, ahora digamos que tenemos 0.323232… aún es sencillo, ahora bien, para el número
0.61029367467310296743597463610293674673102967435974636102936743…
bueno, tal vez ya no sea tan sencillo.
Debemos notar que para 1/d con parte fraccionaria periódica, el periodo máximo que se puede obtener es d-1; ésta es una propiedad demostrada y fácilmente se puede intuir. Bien, de esto sabemos que un algoritmo se volverá más eficiente si comenzamos a buscar a partir del d más grande posible, con ello al momento de encontrar un número con periodo fraccionario decimal d-1, nos detenemos y damos el resultado.
Bien, mi solución guarda el doble del máximo de dígitos que pueda tener cada periodo fraccionario en un arreglo; si tenemos 1/7=0.142857..., el arreglo contendrá 142857142857, y seguido podemos dividir éste arreglo en dos partes iguales y revisamos si éstas son idénticas (d-1 será par). Esto no garantiza que el periodo sea máximo, pues podrían haber, digamos, "subperiodos", desde simples como 1/9=0.111... hasta por ejemplo, 1/977 que tiene periodo 166, pero 976/166=6, es decir, ¡en cada mitad del arreglo habrán 6 periodos de 166 que serán idénticos!, lo que nos podría llevar a pensar incorrectamente que el periodo es 976 (digo incorrectamente pues aunque este último sí es un periodo, no es el que nos interesa).
De lo anterior se sigue inmediatamente un criterio para discernir cuándo el periodo buscado es d-1; i.e. cuando las mitades de una sola mitad del arreglo sean distintas, como en 0.142857 podemos ver que 142$\neq$857, por ejemplo. Tendríamos que expandir o reconsiderar este criterio si es que pudieran haber cantidades impares de subperiodos (¿puedes decir si esto ocurre o no, y por qué?), además de considerar los más simples (mi programa no los considera todos).
El siguiente es un código en Python que resuelve en problema. Yendo un poco más allá del problema de project euler, para d<10^5, funciona en 14.2419729233 segundos bajo Linux (Ubuntu) dando el resultado d=99989.
El problema es el 26 de Project Euler y se puede resumir a: Encuentra el valor de d<1000 para el cual 1/d contiene el periodo más grande en su parte fraccionaria. Mi sorpresa ha sido que la solución se obtiene elegantemente con teoría de números y álgebra abstracta al resolver el algoritmo discreto ${10^k\equiv1\mod{n}}$. Sin embargo son herramientas de las cuales aún no tengo pleno conocimiento; como sea, quien esté interesado puede consultar esta liga.
Estuve bastante ansioso por resolver el problema, y finalmente lo hice, aunque fuera de forma rudimentaria, pero encontrando algunas cosillas interesantes.
Lo difícil fue determinar cuándo la parte fraccionaria decimal era periódica. Digamos que tenemos 0.3333… bueno, resulta muy sencillo, ahora digamos que tenemos 0.323232… aún es sencillo, ahora bien, para el número
0.61029367467310296743597463610293674673102967435974636102936743…
bueno, tal vez ya no sea tan sencillo.
Debemos notar que para 1/d con parte fraccionaria periódica, el periodo máximo que se puede obtener es d-1; ésta es una propiedad demostrada y fácilmente se puede intuir. Bien, de esto sabemos que un algoritmo se volverá más eficiente si comenzamos a buscar a partir del d más grande posible, con ello al momento de encontrar un número con periodo fraccionario decimal d-1, nos detenemos y damos el resultado.
Bien, mi solución guarda el doble del máximo de dígitos que pueda tener cada periodo fraccionario en un arreglo; si tenemos 1/7=0.142857..., el arreglo contendrá 142857142857, y seguido podemos dividir éste arreglo en dos partes iguales y revisamos si éstas son idénticas (d-1 será par). Esto no garantiza que el periodo sea máximo, pues podrían haber, digamos, "subperiodos", desde simples como 1/9=0.111... hasta por ejemplo, 1/977 que tiene periodo 166, pero 976/166=6, es decir, ¡en cada mitad del arreglo habrán 6 periodos de 166 que serán idénticos!, lo que nos podría llevar a pensar incorrectamente que el periodo es 976 (digo incorrectamente pues aunque este último sí es un periodo, no es el que nos interesa).
De lo anterior se sigue inmediatamente un criterio para discernir cuándo el periodo buscado es d-1; i.e. cuando las mitades de una sola mitad del arreglo sean distintas, como en 0.142857 podemos ver que 142$\neq$857, por ejemplo. Tendríamos que expandir o reconsiderar este criterio si es que pudieran haber cantidades impares de subperiodos (¿puedes decir si esto ocurre o no, y por qué?), además de considerar los más simples (mi programa no los considera todos).
El siguiente es un código en Python que resuelve en problema. Yendo un poco más allá del problema de project euler, para d<10^5, funciona en 14.2419729233 segundos bajo Linux (Ubuntu) dando el resultado d=99989.
from decimal import *
import time
t0 = time.time()
for i in range((10**5)-1, 1, -2):
getcontext().prec = 2*(i-1)
cad = str(Decimal(1)/Decimal(i))
if len(cad) > i+1:
a, b = [], []
for x in range(i+1, 2*i):
a.append(cad[x-i+1])
b.append(cad[x])
c = 0
for x in range(i-2):
if a[x] == a[x+1]:
c += 1
if c >= i-2:
continue
else:
if a != b:
continue
else:
c, d = [], []
for n in range(0,len(a)/2):
c.append(a[n])
d.append(a[(len(a)/2)+n])
if c == d:
continue
else:
print "Respuesta:",i
break
print "Duracion:",time.time()-t0, "segundos"
No comments:
Post a Comment