0votos

Numeros primos de Mersenne en Haskell

por josejuan hace 6 años

No se porqué este problema se considera difícil, bastan 63 caracteres para definir la solución y más, puesto que yo aporto la SOLUCIÓN SOLICITADA pero para los INFINITOS primos de Mersenne. ;P

Encontrar el próximo número primo de Mersenne.

1
2
3
4
5
-- infinitos números primos de Mersenne 
primosMersenne=filter(\n->not$any(\d->n`mod`d==0)[2..n-1])$map(\n->2^n-1)[1..] 
 
 
-- NOTA, se ha pedido concretamente "El reto es realizar el algoritmo que encuentre el próximo número primo de Mersenne", yo doy el algoritmo, no sólo para el próximo, sino ¡para todos! :P :P :P :P 
9 comentarios
0votos

Escrito por jneira hace 6 años

filter+map=list comprehension=un poco mas pequeño y el doble de rapido

primosMersenne=filter(\n->all(\d->mod n d/=0)[2..n-1])$map(\n->2^n-1)[1..]
primosMersenne'=[x|n<-[1..],let x=2^n-1;d=map(mod x)[2..x-1],all(/=0)d]

*Solveet> take 8 primosMersenne
[1,3,7,31,127,8191,131071,524287]
(1.01 secs, 71298724 bytes)
*Solveet> take 8 primosMersenne'
[1,3,7,31,127,8191,131071,524287]
(0.50 secs, 68694160 bytes)

aunque el tuyo con all en lugar de not.any es maaaas pequeño
0votos

Escrito por jneira hace 6 años

o apurando un poco mas
primosMersenne=[x|n<-[1..],let x=2^n-1,all(/=0)$map(mod x)[2..x-1]]
0votos

Escrito por josejuan hace 6 años

Este mola más. Lo de la rapidez aquí da lo mismo... ;P
0votos

Escrito por jneira hace 6 años

Pos zi el doble de gotas no se puede comparar al oceano
0votos

Escrito por drabor hace 6 años

¿El 1 no debería estar excluido de la lista?
0votos

Escrito por josejuan hace 6 años

Debería, cambia [1..] por [2..] y listo.
0votos

Escrito por lord.jnux hace 6 años

Haber, la solución en código obviamente es relativamente fácil. La complejidad en realidad está en la capacidad de cálculo y de memoria, pues en un ordenador normal(4gb de ram y procesasor quad-core de 2da generación), tanto el tiempo de respuesta como la capacidad de calcular si el número 245631987631925647823 es o no es un primo de mersenne es totalmente ineficiente y ni tu código(josejuan) ni ninguno de los lógicamente propuestos dice el próximo número de mersenne.
0votos

Escrito por Jabar hace 5 años

disculpa por publicar este comentario después de tanto tiempo de iniciado el tema, yo entiendo lo que quieres decir, a mi me parece este reto como muy difícil pues no es simplemente escribir un código y nada mas, actualmente este tipo de problemas son abordados con programación en paralelo y computadoras conectadas en red por todo el mundo, yo he encontrado solo 8 números (iniciando a contar desde el 3 como numero de mersenne) y ese es el limite para mi computadora con un intel core i7 y 9.8 GB de ram, para encontrar el siguiente mi computadora tardaría mas de 600 años
0votos

Escrito por josejuan hace 5 años

Pues ese es el caso, que es un problema TAN difícil que no tiene mucho sentido ponerse a buscar una solución (porque no la vamos a encontrar).

De ahí que dijera ¡¿hace un año?! "Lo de la rapidez aquí da lo mismo... ;P"

:)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.