A un primo de un múltiplo del inverso en Haskell
La semana pasada en el blog Números y algo más se planteó el problema Igual a un múltiplo del “inverso” mas/ menos un primo cuyo enunciado es el siguiente:
El número 21 es el menor número que es igual a un múltiplo de sí mismo dado vuelta (2 x12) más/menos (-3) un primo menor que él:
21 = 12 x 2 – 3
El siguiente es:
31 = 13 x 2 + 5
En este caso vemos que el número original también es primo.La solución 13 = 31 x 6 – 173 no es válida ya que 173 a pesar de ser primo es mayor que 13.
Buscando sólo primos que tengan esta propiedad el siguiente que cumple es el 41 y para el cual tenemos dos soluciones:
41 = 14 x 2 + 13
41 = 14 x 5 – 29El primer primo que tiene cuatro soluciones es el 61:
61 = 16 x 2 + 29
61 = 16 x 3 + 13
61 = 16 x 4 – 3
61 = 16 x 5 – 19¿Cuál es el primer primo que tiene cinco soluciones? ¿y el primero que tiene seis?
A partir de dicho problema he escrito en LógicaMente dos relaciones de ejercicios. La primera usando una definición elemental de números primos y la segunda usando la librería Data.Numbers.Primes. Finalmente se compara la eficiencia de ambas definiciones para resolver el problema.
La primera relación 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 |
-- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- divisores :: Int -> [Int] -- tal que (divisores n) es la lista de los divisores de n. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] -- --------------------------------------------------------------------- divisores :: Int -> [Int] divisores n = [x | x <- [1..n], n `mod` x == 0] -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la propiedad -- esPrimo :: Int -> Bool -- tal que (esPrimo n) se verifica si n es primo. Por ejemplo, -- esPrimo 7 == True -- esPrimo 9 == False -- --------------------------------------------------------------------- esPrimo :: Int -> Bool esPrimo n = divisores n == [1,n] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la constante -- primos :: [Int] -- tal que primos es la lista de los números primos. Por ejemplo, -- take 15 primos == [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47] -- --------------------------------------------------------------------- primos :: [Int] primos = [n | n <- [1..], esPrimo n] -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- primosMenores :: Int -> [Int] -- tal que (primosMenores x) es la lista de los números primos menores -- que x. Por ejemplo, -- primosMenores 47 == [2,3,5,7,11,13,17,19,23,29,31,37,41,43] -- --------------------------------------------------------------------- primosMenores :: Int -> [Int] primosMenores x = [n | n <- [1..x-1], esPrimo n] -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- inverso :: Int -> Int -- tal que (inverso x) es el número obtenido escibiendo las cifras de x -- en orden inverso. Por ejemplo, -- inverso 325 == 523 -- inverso 320 == 23 -- --------------------------------------------------------------------- inverso :: Int -> Int inverso n = read (reverse (show n)) -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- esSolucion :: Int -> (Int,Int) -> Bool -- tal que (esSolucion x (m,p)) se verifica si se cumplen las siguientes -- condiciones: -- * x == (inverso x)*m+p -- * abs p < x -- * esPrimo (abs p) -- Por ejemplo, -- esSolucion 21 (2,-3) == True -- esSolucion 31 (2,5) == True -- esSolucion 13 (6,-173) == False -- --------------------------------------------------------------------- esSolucion :: Int -> (Int,Int) -> Bool esSolucion x (m,p) = x == (inverso x)*m+p && abs p < x && esPrimo (abs p) -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- soluciones :: Int -> [(Int,Int)] -- tal que (soluciones x) es la lista de las soluciones de x. Por -- ejemplo, -- soluciones 21 == [(2,-3)] -- soluciones 31 == [(2,5)] -- soluciones 41 == [(2,13),(5,-29)] -- soluciones 61 == [(3,13),(2,29),(4,-3),(5,-19)] -- --------------------------------------------------------------------- soluciones :: Int -> [(Int,Int)] soluciones x = [(m,p) | m <- [1..2*(x-1) `div` y], let p = x-y*m, esPrimo (abs p)] where y = inverso x -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- prop_soluciones :: Int -> Bool -- tal que (prop_soluciones x) se verifica si para todo y menor que x, -- los elementos de (soluciones y) son soluciones de y. Por ejemplo, -- prop_soluciones 100 == True -- --------------------------------------------------------------------- prop_soluciones :: Int -> Bool prop_soluciones x = and [esSolucion y p | y <- [1..x-1], p <- soluciones y] -- --------------------------------------------------------------------- -- Ejercicio 9. Un número es especial si es igual a un múltiplo de sí -- mismo dado vuelta más/menos un primo menor que él. Por ejemplo, el 21 -- es especial porque -- 21 = 12 x 2 - 3 -- Definir la propiedad -- especial :: Int -> Bool -- tal que (especial x) se verifica si x es un número especial. Por -- ejemplo, -- especial 21 == True -- especial 22 == False -- --------------------------------------------------------------------- especial :: Int -> Bool especial x = not (null (soluciones x)) -- --------------------------------------------------------------------- -- Ejercicio 10. Un número es especial de grado n si tiene n soluciones. -- -- Definir la propiedad -- especialDeGrado :: Int -> Int -> Bool -- tal que (especialDeGrado x n) se verifica si x es un número especial -- de grado n. Por ejemplo, -- especialDeGrado 21 1 == True -- especialDeGrado 21 2 == False -- especialDeGrado 41 2 == True -- --------------------------------------------------------------------- especialDeGrado :: Int -> Int -> Bool especialDeGrado x n = length (soluciones x) == n -- --------------------------------------------------------------------- -- Ejercicio 11. Definir la función -- menorPrimoEspecialDeGrado :: Int -> Int -- tal que (menorPrimoEspecialDeGrado n) es el menor primo especial de -- grado n. Por ejemplo, -- menorPrimoEspecialDeGrado 1 == 31 -- menorPrimoEspecialDeGrado 2 == 41 -- menorPrimoEspecialDeGrado 3 == 71 -- menorPrimoEspecialDeGrado 4 == 61 -- --------------------------------------------------------------------- menorPrimoEspecialDeGrado :: Int -> Int menorPrimoEspecialDeGrado n = head [x | x <- primos, especialDeGrado x n] -- --------------------------------------------------------------------- -- Ejercicio 12. Calcular las respuestas a las dos preguntas del -- problema: -- ¿Cuál es el primer primo que tiene cinco soluciones? ¿y el -- primero que tiene seis? -- --------------------------------------------------------------------- -- El cálculo es -- ghci> menorPrimoEspecialDeGrado 5 -- 6421 -- ghci> menorPrimoEspecialDeGrado 6 -- 8501 -- --------------------------------------------------------------------- -- Ejercicio 13. Calcular los costes de los cálculos anteriores. -- --------------------------------------------------------------------- -- El cálculo es -- ghci> :set +s -- ghci> menorPrimoEspecialDeGrado 5 -- 6421 -- (2.99 secs, 335729840 bytes) -- ghci> menorPrimoEspecialDeGrado 6 -- 8501 -- (5.46 secs, 577386544 bytes) |
La segunda relación es
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 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Numbers.Primes -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- inverso :: Int -> Int -- tal que (inverso x) es el número obtenido escibiendo las cifras de x -- en orden inverso. Por ejemplo, -- inverso 325 == 523 -- inverso 320 == 23 -- --------------------------------------------------------------------- inverso :: Int -> Int inverso n = read (reverse (show n)) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- esSolucion :: Int -> (Int,Int) -> Bool -- tal que (esSolucion x (m,p)) se verifica si se cumplen las siguientes -- condiciones: -- * x == (inverso x)*m+p -- * abs p < x -- * esPrimo (abs p) -- Por ejemplo, -- esSolucion 21 (2,-3) == True -- esSolucion 31 (2,5) == True -- esSolucion 13 (6,-173) == False -- --------------------------------------------------------------------- esSolucion :: Int -> (Int,Int) -> Bool esSolucion x (m,p) = x == (inverso x)*m+p && abs p < x && isPrime (abs p) -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- soluciones :: Int -> [(Int,Int)] -- tal que (soluciones x) es la lista de las soluciones de x. Por -- ejemplo, -- soluciones 21 == [(2,-3)] -- soluciones 31 == [(2,5)] -- soluciones 41 == [(2,13),(5,-29)] -- soluciones 61 == [(3,13),(2,29),(4,-3),(5,-19)] -- --------------------------------------------------------------------- soluciones :: Int -> [(Int,Int)] soluciones x = [(m,p) | m <- [1..2*(x-1) `div` y], let p = x-y*m, isPrime (abs p)] where y = inverso x -- --------------------------------------------------------------------- -- Ejercicio 4. Un número es especial si es igual a un múltiplo de sí -- mismo dado vuelta más/menos un primo menor que él. Por ejemplo, el 21 -- es especial porque -- 21 = 12 x 2 - 3 -- Definir la propiedad -- especial :: Int -> Bool -- tal que (especial x) se verifica si x es un número especial. Por -- ejemplo, -- especial 21 == True -- especial 22 == False -- --------------------------------------------------------------------- especial :: Int -> Bool especial x = not (null (soluciones x)) -- --------------------------------------------------------------------- -- Ejercicio 5. Un número es especial de grado n si tiene n soluciones. -- -- Definir la propiedad -- especialDeGrado :: Int -> Int -> Bool -- tal que (especialDeGrado x n) se verifica si x es un número especial -- de grado n. Por ejemplo, -- especialDeGrado 21 1 == True -- especialDeGrado 21 2 == False -- especialDeGrado 41 2 == True -- --------------------------------------------------------------------- especialDeGrado :: Int -> Int -> Bool especialDeGrado x n = length (soluciones x) == n -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- menorPrimoEspecialDeGrado :: Int -> Int -- tal que (menorPrimoEspecialDeGrado n) es el menor primo especial de -- grado n. Por ejemplo, -- menorPrimoEspecialDeGrado 1 == 31 -- menorPrimoEspecialDeGrado 2 == 41 -- menorPrimoEspecialDeGrado 3 == 71 -- menorPrimoEspecialDeGrado 4 == 61 -- --------------------------------------------------------------------- menorPrimoEspecialDeGrado :: Int -> Int menorPrimoEspecialDeGrado n = head [x | x <- primes, especialDeGrado x n] -- --------------------------------------------------------------------- -- Ejercicio 7. Calcular las respuestas a las dos preguntas del -- problema: -- ¿Cuál es el primer primo que tiene cinco soluciones? ¿y el -- primero que tiene seis? -- --------------------------------------------------------------------- -- El cálculo es -- ghci> menorPrimoEspecialDeGrado 5 -- 6421 -- ghci> menorPrimoEspecialDeGrado 6 -- 8501 -- --------------------------------------------------------------------- -- Ejercicio 8. Calcular los costes de los cálculos anteriores. -- --------------------------------------------------------------------- -- El cálculo es -- ghci> menorPrimoEspecialDeGrado 5 -- 6421 -- (0.02 secs, 4207796 bytes) -- ghci> menorPrimoEspecialDeGrado 6 -- 8501 -- (0.04 secs, 6299076 bytes) |
La comparación del espacio y tiempo utilizado es