El desafío matemático “Un número curioso” en Haskell
En El País del día 16 se presentó el desafío matemático Un número curios cuyo enunciado es el siguiente:
El equipo que preparamos los desafíos matemáticos hemos decidido abonarnos durante todo el año a un número de la Lotería. Para elegir ese número, que debe estar comprendido entre el 0 y el 99.999, pusimos como condición que tuviese las cinco cifras distintas y que, además, cumpliese alguna otra propiedad interesante. Finalmente hemos conseguido un número que tiene la siguiente propiedad: si numeramos los meses del año del 1 al 12, en cualquier mes del año ocurre que al restar a nuestro número de lotería el número del mes anterior, el resultado es divisible por el número del mes en el que estemos. Y esto sucede para cada uno de los meses del año.
Es decir, si llamamos L a nuestro número, tenemos por ejemplo que en marzo L-2 es divisible entre 3 y en diciembre L-11 es divisible entre 12.
El reto que os planteamos es que nos digáis a qué número de Lotería estamos abonados.
He elaborado una relación de ejercicios (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) en la que se generaliza el problema y se resuelve con Haskell de cuatro maneras distintas. La relación de ejercicios es la siguiente
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List (nub) -- --------------------------------------------------------------------- -- § 1ª solución (por fuerza bruta) -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 1. Un número n es casi curioso de orden k si tiene la -- siguiente propiedad: para cada i entre 1 y k, n-i es divisible por i. -- -- Definir la función -- esCasiCurioso :: Integer -> Integer -> Bool -- tal que (esCasiCurioso k n) se verifica si n es casi curioso de orden -- k. Por ejemplo, -- esCasiCurioso 3 17 == True -- esCasiCurioso 4 17 == False -- --------------------------------------------------------------------- esCasiCurioso :: Integer -> Integer -> Bool esCasiCurioso k n = and [(n-i+1) `mod` i == 0 | i <- [1..k]] -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- casiCuriosos1 :: Integer -> [Integer] -- tal que (casiCuriosos1 k) es la lista de los números casi curiosos de -- orden k. Por ejemplo, -- take 5 (casiCuriosos1 4) == [11,23,35,47,59] -- --------------------------------------------------------------------- casiCuriosos1 :: Integer -> [Integer] casiCuriosos1 k = [n | n <- [1..], esCasiCurioso k n] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- conCifras :: Integer -> [Integer] -> [Integer] -- tal que (conCifras k xs) es la lista de números con k cifras de la -- lista creciente de números xs. Por ejemplo, -- conCifras 2 [7,17..] == [17,27,37,47,57,67,77,87,97] -- --------------------------------------------------------------------- conCifras :: Integer -> [Integer] -> [Integer] conCifras k xs = takeWhile (<=10^k-1) (dropWhile (<10^(k-1)) xs) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- cifrasDistintas :: Integer -> Bool -- tal que (cifrasDistintas n) se verifica si n es un número con sus -- cifras distintas. Por ejemplo, -- cifrasDistintas 325476 == True -- cifrasDistintas 325426 == False -- --------------------------------------------------------------------- cifrasDistintas :: Integer -> Bool cifrasDistintas n = length cifras == length (nub cifras) where cifras = show n -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- conCifrasDistintas :: [Integer] -> [Integer] -- tal que (conCifrasDistintas xs) es la lista de números de xs que -- tienen sus cifras distintas. Por ejemplo, -- conCifrasDistintas [27719,55439,83159] == [83159] -- --------------------------------------------------------------------- conCifrasDistintas :: [Integer] -> [Integer] conCifrasDistintas = filter cifrasDistintas -- --------------------------------------------------------------------- -- Ejercicio 6. Un número n es curioso si es curioso de tipo A y sus -- cifras son distintas. -- -- Definir la función -- curiosos1 :: Integer -> [Integer] -- tal que (curiosos1 k m) es la lista de los números curiosos de orden -- k con m cifras. Por ejemplo, -- curiosos1 9 4 == [2519,5039] -- --------------------------------------------------------------------- curiosos1 :: Integer -> Integer -> [Integer] curiosos1 k m = conCifrasDistintas (conCifras m (casiCuriosos1 k)) -- --------------------------------------------------------------------- -- Ejercicio 7. Calcular la solución del desafío matemático. -- --------------------------------------------------------------------- -- El cálculo es -- ghci> head (curiosos1 12 5) -- 83159 -- --------------------------------------------------------------------- -- § 2ª solución (con casiCuriosos por recursión) -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 8. Definir, por recursión, la función -- casiCuriosos2 :: Integer -> [Integer] -- tal que (casiCuriosos2 k) es la lista de los números casi curiosos de -- orden k. Por ejemplo, -- take 5 (casiCuriosos2 4) == [11,23,35,47,59] -- --------------------------------------------------------------------- casiCuriosos2 :: Integer -> [Integer] casiCuriosos2 1 = [1..] casiCuriosos2 k = [n | n <- casiCuriosos2 (k-1), (n-k+1) `mod` k == 0] -- --------------------------------------------------------------------- -- Ejercicio 9. Definir la función -- curiosos2 :: Integer -> [Integer] -- tal que (curiosos2 k m) es la lista de los números curiosos de orden -- k con m cifras. Por ejemplo, -- curiosos2 9 4 == [2519,5039] -- --------------------------------------------------------------------- curiosos2 :: Integer -> Integer -> [Integer] curiosos2 k m = conCifrasDistintas (conCifras m (casiCuriosos2 k)) -- --------------------------------------------------------------------- -- Ejercicio 10. Comparar los recursos necesarios para evaluar las -- siguientes expresiones -- head (curiosos1 12 7) -- head (curiosos2 12 7) -- --------------------------------------------------------------------- -- La comparación es -- ghci> head (curiosos1 12 7) -- 1025639 -- (19.05 secs, 770789772 bytes) -- ghci> head (curiosos2 12 7) -- 1025639 -- (8.34 secs, 315892320 bytes) -- --------------------------------------------------------------------- -- § Por recursión -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 11. Definir, por recursión, la función -- curiosos3 :: Integer -> Integer -> [Integer] -- tal que (curiosos3 k m) es la lista de los números curiosos de orden -- k con m cifras. Por ejemplo, -- curiosos3 9 4 == [2519,5039] -- --------------------------------------------------------------------- curiosos3 :: Integer -> Integer -> [Integer] curiosos3 1 m = conCifrasDistintas [10^(m-1)..10^m-1] curiosos3 k m = [n | n <- curiosos3 (k-1) m, (n-k+1) `mod` k == 0] -- --------------------------------------------------------------------- -- Ejercicio 12. Comparar los recursos necesarios para evaluar las -- siguientes expresiones -- head (curiosos2 12 7) -- head (curiosos3 12 7) -- --------------------------------------------------------------------- -- La comparación es -- ghci> head (curiosos2 12 7) -- 1025639 -- (8.34 secs, 315892320 bytes) -- ghci> head (curiosos3 12 7) -- 1025639 -- (0.19 secs, 14468104 bytes) -- --------------------------------------------------------------------- -- § 4ª solución (por propiedades observadas) -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 13. Definir la función -- diferencias :: [Integer] -> [Integer] -- tal que (diferencias xs) es la lista de la diferencia de cada -- elemento de xs por su anterior. Por ejemplo, -- diferencias [3,5,6,11] == [2,1,5] -- --------------------------------------------------------------------- diferencias :: [Integer] -> [Integer] diferencias xs = zipWith (-) (tail xs) xs -- --------------------------------------------------------------------- -- Ejercicio 14. Calcular el valor de las siguientes expresiones -- diferencias (take 5 (casiCuriosos1 2)) -- diferencias (take 5 (casiCuriosos1 3)) -- diferencias (take 5 (casiCuriosos1 4)) -- diferencias (take 5 (casiCuriosos1 5)) -- diferencias (take 5 (casiCuriosos1 5)) -- ¿Qué se observa? -- --------------------------------------------------------------------- -- El cálculo es -- ghci> diferencias (take 5 (casiCuriosos1 2)) -- [2,2,2,2] -- ghci> diferencias (take 5 (casiCuriosos1 3)) -- [6,6,6,6] -- ghci> diferencias (take 5 (casiCuriosos1 4)) -- [12,12,12,12] -- ghci> diferencias (take 5 (casiCuriosos1 5)) -- [60,60,60,60] -- ghci> diferencias (take 5 (casiCuriosos1 6)) -- [60,60,60,60] -- -- Se observa que todas las diferencias son iguales (es decir son -- progresiones aritméticas). -- --------------------------------------------------------------------- -- Ejercicio 15. Definir la función -- mcm :: [Integer] -> Integer -- tal que (mcm xs) es el mínimo común múltiplo de los números de xs. -- Por ejemplo, -- mcm [2,6,4,5] == 60 -- --------------------------------------------------------------------- mcm :: [Integer] -> Integer mcm = foldr1 lcm -- --------------------------------------------------------------------- -- Ejercicio 16. Calcular el valor de (mcm [1..k]) para k entre 1 y 6. -- ¿Qué relación se observa a partir de los cálculos del ejercicio 14? -- --------------------------------------------------------------------- -- El cálculo es -- ghci> [(k,mcm [1..k]) | k <- [1..6]] -- [(1,1),(2,2),(3,6),(4,12),(5,60),(6,60)] -- -- Se observa que, para cada k, (casiCuriosos1 5) es una progresión -- aritmética cuya diferencia es el mínimo común múltiplo de 1,2,..k. -- --------------------------------------------------------------------- -- Ejercicio 17. Calcular el valor de las siguientes expresiones -- head (casiCuriosos1 2) -- head (casiCuriosos1 3) -- head (casiCuriosos1 4) -- head (casiCuriosos1 5) -- head (casiCuriosos1 6) -- ¿Qué relación se observa entre (head (casiCuriosos1 k)) y k? -- --------------------------------------------------------------------- -- El cálculo es -- ghci> head (casiCuriosos1 2) -- 1 -- ghci> head (casiCuriosos1 3) -- 5 -- ghci> head (casiCuriosos1 4) -- 11 -- ghci> head (casiCuriosos1 5) -- 59 -- ghci> head (casiCuriosos1 6) -- 59 -- -- Se observa que el primer elemento de (casiCuriosos1 k) es el mínimo -- común múltiplo de 1,2,..k menos 1. -- --------------------------------------------------------------------- -- Ejercicio 18. Usando las observaciones de los ejercicios anteriores, -- definir la función -- casiCuriosos4 :: Integer -> [Integer] -- tal que (casiCuriosos4 k) es la lista de los números casi curiosos de -- orden k. Por ejemplo, -- take 5 (casiCuriosos4 4) == [11,23,35,47,59] -- --------------------------------------------------------------------- casiCuriosos4 :: Integer -> [Integer] casiCuriosos4 k = [a-1,2*a-1..] where a = mcm [1..k] -- --------------------------------------------------------------------- -- Ejercicio 19. Definir la función -- curiosos4 :: Integer -> Integer -> [Integer] -- tal que (curiosos4 k m) es la lista de los números curiosos de orden -- k con m cifras. Por ejemplo, -- curiosos4 9 4 == [2519,5039] -- --------------------------------------------------------------------- curiosos4 :: Integer -> Integer -> [Integer] curiosos4 k m = conCifrasDistintas (conCifras m (casiCuriosos4 k)) -- --------------------------------------------------------------------- -- Ejercicio 20. Comparar los recursos necesarios para evaluar las -- siguientes expresiones -- head (curiosos3 12 7) -- head (curiosos4 12 7) -- --------------------------------------------------------------------- -- La comparación es -- ghci> head (curiosos3 12 7) -- 1025639 -- (0.16 secs, 14297500 bytes) -- ghci> head (curiosos4 12 7) -- 1025639 -- (0.01 secs, 0 bytes) -- --------------------------------------------------------------------- -- Ejercicio 21. Comparar los recursos necesarios para resolver el -- desafío con las cuatro definiciones. -- --------------------------------------------------------------------- -- El cálculo es -- ghci> head (curiosos1 12 5) -- 83159 -- (1.48 secs, 62312260 bytes) -- ghci> head (curiosos2 12 5) -- 83159 -- (0.69 secs, 25715892 bytes) -- ghci> head (curiosos3 12 5) -- 83159 -- (0.62 secs, 41017896 bytes) -- ghci> head (curiosos4 12 5) -- 83159 -- (0.01 secs, 750248 bytes) -- --------------------------------------------------------------------- -- § Nota final -- -- --------------------------------------------------------------------- -- Se podría haber planteado desde el principio la cuarta solución -- observando que los números casi curiosos de orden k son las -- soluciones del sistema de ecuaciones -- x = 1 (mod 2) -- x = 2 (mod 3) -- ... -- x = k-1 (mod k) |