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

solucion1 :: Int
solucion1 = head [n | n <- [1..1983], length (divisores1 n) == m]
    where m = maximum [length (divisores1 n) | n <- [1..1983]]

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.

divisores1 :: Int -> [Int]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

1 2	divisores1 :: Int -> [Int] divisores1 n = [x \| x <- [1..n], n `rem` x == 0]

El cálculo con la primera definición es

ghci> solucion1
1680
(9.00 secs, 383804180 bytes)

ghci> solucion1

1680

(9.00 secs, 383804180 bytes)

En la segunda definición se cambia la definición de divisores

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]]

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

ghci> solucion2
1680
(4.69 secs, 192555880 bytes)

ghci> solucion2

1680

(4.69 secs, 192555880 bytes)

En la tercera definición se ordenan los pares

solucion3 :: Int
solucion3 = 
    snd (maximum [(length (divisores2 n),n) | n <- [1..1983]])

solucion3 :: Int

solucion3 =

snd (maximum [(length (divisores2 n),n) | n <- [1..1983]])

El cálculo con la tercera definición es

ghci> solucion3
1680
(2.76 secs, 112406152 bytes)

ghci> solucion3

1680

(2.76 secs, 112406152 bytes)

Se observa que el tiempo se ha reducido de 9.00 segundos a 2.76.

Se puede imprimir o compartir con