0votos

Finales de Mersenne en Haskell

por josejuan hace 6 años

Calculo cualquier nº de dígitos de cualquier nº Mersenne. Solo hay que fijarse, que el módulo de un número, es el módulo del producto de los módulos de cualquieras factores. Y que la suma o resta del número, puede hacerse sobre el módulo. Así, podemos reducir la potencia M-ésima y luego restar uno a su módulo. Varios speedups son posibles (yo hago bipartición), memoize, etc... pero éste no es lento.

Calcular los últimos dígitos del mayor número primo de Mersenne descubierto,

1
2
3
4
5
6
7
8
digitosMersenne m n = -1 + r m where {r q = if q < n then 2^q else mod (r (q `div` 2) * r (q - q `div` 2)) p; p = 10^n} 
 
 
{-- 
Prelude> let digitosMersenne m n = -1 + r m where {r q = if q < n then 2^q else mod (r (q `div` 2) * r (q - q `div` 2)) p; p = 10^n} 
Prelude> digitosMersenne 43112609 30 
887478265780022181166697152511 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.