I1M2012: Número con mayor cantidad de divisores
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto para la Olimpiada Internacional de Matemáticas de 1983. Su enunciado es
”¿Cuál de los números 1, 2, …, 1983 tiene mayor número de divisores?”
Se van a presentar distintas soluciones y comparar sus eficiciencias. La primera definición es
|
1 2 3 |
solucion1 :: Int solucion1 = head [n | n <- [1..1983], length (divisores1 n) == m] where m = maximum [length (divisores1 n) | n <- [1..1983]] |
donde (divisores1 n) es el conjunto de los divisores de n.
|
1 2 |
divisores1 :: Int -> [Int] divisores1 n = [x | x <- [1..n], n `rem` x == 0] |
El cálculo con la primera definición es
|
1 2 3 |
ghci> solucion1 1680 (9.00 secs, 383804180 bytes) |
En la segunda definición se cambia la definición de divisores
|
1 2 3 4 5 6 |
divisores2 :: Int -> [Int] divisores2 n = n : [x | x <- [1..div n 2], n `rem` x == 0] solucion2 :: Int solucion2 = head [n | n <- [1..1983], length (divisores2 n) == m] where m = maximum [length (divisores2 n) | n <- [1..1983]] |
El cálculo con la segunda definición es
|
1 2 3 |
ghci> solucion2 1680 (4.69 secs, 192555880 bytes) |
En la tercera definición se ordenan los pares
|
1 2 3 |
solucion3 :: Int solucion3 = snd (maximum [(length (divisores2 n),n) | n <- [1..1983]]) |
El cálculo con la tercera definición es
|
1 2 3 |
ghci> solucion3 1680 (2.76 secs, 112406152 bytes) |
Se observa que el tiempo se ha reducido de 9.00 segundos a 2.76.