Pares definidos por su MCD y su MCM
Definir las siguientes funciones
1 2 |
pares :: Integer -> Integer -> [(Integer,Integer)] nPares :: Integer -> Integer -> Integer |
tales que
- (pares a b) es la lista de los pares de números enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
1 2 3 4 5 6 7 |
pares 3 3 == [(3,3)] pares 4 12 == [(4,12),(12,4)] pares 2 12 == [(2,12),(4,6),(6,4),(12,2)] pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)] pares 2 7 == [] pares 12 3 == [] length (pares 3 (product [3,5..91])) == 8388608 |
- (nPares a b) es el número de pares de enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
1 2 3 4 5 6 7 8 |
nPares 3 3 == 1 nPares 4 12 == 2 nPares 2 12 == 4 nPares 2 60 == 8 nPares 2 7 == 0 nPares 12 3 == 0 nPares 3 (product [3..3*10^4]) `mod` (10^12) == 477999992832 length (show (nPares 3 (product [3..3*10^4]))) == 977 |
Soluciones
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 |
import Data.Numbers.Primes (primeFactors) import Data.List (genericLength, group, nub, sort, subsequences) import Test.QuickCheck -- 1ª definición de pares -- ====================== pares1 :: Integer -> Integer -> [(Integer,Integer)] pares1 a b = [(x,y) | x <- [1..b] , y <- [1..b] , gcd x y == a , lcm x y == b] -- 2ª definición de pares -- ====================== pares2 :: Integer -> Integer -> [(Integer,Integer)] pares2 a b = [(x,y) | x <- [a,a+a..b] , y <- [a,a+a..b] , gcd x y == a , lcm x y == b] -- Comparación de eficiencia -- λ> length (pares1 3 (product [3,5..11])) -- 16 -- (95.12 secs, 86,534,165,528 bytes) -- λ> length (pares2 3 (product [3,5..11])) -- 16 -- (15.80 secs, 14,808,762,128 bytes) -- 3ª definición de pares -- ====================== pares3 :: Integer -> Integer -> [(Integer,Integer)] pares3 a b = [(x,y) | x <- [a,a+a..b] , c `rem` x == 0 , let y = c `div` x , gcd x y == a ] where c = a * b -- Comparacioń de eficiencia -- λ> length (pares2 3 (product [3,5..11])) -- 16 -- (15.80 secs, 14,808,762,128 bytes) -- λ> length (pares3 3 (product [3,5..11])) -- 16 -- (0.01 secs, 878,104 bytes) -- 4ª definición de pares -- ====================== -- Para la cuarta definición de pares se observa la relación con los -- factores primos -- λ> [(primeFactors x, primeFactors y) | (x,y) <- pares1 2 12] -- [([2],[2,2,3]),([2,2],[2,3]),([2,3],[2,2]),([2,2,3],[2])] -- λ> [primeFactors x | (x,y) <- pares1 2 12] -- [[2],[2,2],[2,3],[2,2,3]] -- λ> [primeFactors x | (x,y) <- pares1 2 60] -- [[2],[2,2],[2,3],[2,5],[2,2,3],[2,2,5],[2,3,5],[2,2,3,5]] -- λ> [primeFactors x | (x,y) <- pares1 6 60] -- [[2,3],[2,2,3],[2,3,5],[2,2,3,5]] -- λ> [primeFactors x | (x,y) <- pares1 2 24] -- [[2],[2,3],[2,2,2],[2,2,2,3]] -- Se observa que cada pares se obtiene de uno de los subconjuntos de los -- divisores primos de b/a. Por ejemplo, -- λ> (a,b) = (2,24) -- λ> b `div` a -- 12 -- λ> primeFactors it -- [2,2,3] -- λ> group it -- [[2,2],[3]] -- λ> subsequences it -- [[],[[2,2]],[[3]],[[2,2],[3]]] -- λ> map concat it -- [[],[2,2],[3],[2,2,3]] -- λ> map product it -- [1,4,3,12] -- λ> [(a * x, b `div` x) | x <- it] -- [(2,24),(8,6),(6,8),(24,2)] -- A partir de la observación se construye la siguiente definición pares4 :: Integer -> Integer -> [(Integer,Integer)] pares4 a b | b `mod` a /= 0 = [] | otherwise = [(a * x, b `div` x) | x <- map (product . concat) ((subsequences . group . primeFactors) (b `div` a))] -- Nota. La función pares4 calcula el mismo conjunto que las anteriores, -- pero no necesariamente en el mismo orden. Por ejemplo, -- λ> pares3 2 60 -- [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)] -- λ> pares4 2 60 -- [(2,60),(4,30),(6,20),(12,10),(10,12),(20,6),(30,4),(60,2)] -- λ> pares3 2 60 == sort (pares4 2 60) -- True -- Comparacioń de eficiencia -- λ> length (pares3 3 (product [3,5..17])) -- 64 -- (4.44 secs, 2,389,486,440 bytes) -- λ> length (pares4 3 (product [3,5..17])) -- 64 -- (0.00 secs, 177,704 bytes) -- Propiedades de equivalencia de pares -- ==================================== prop_pares :: Integer -> Integer -> Property prop_pares a b = a > 0 && b > 0 ==> all (== pares1 a b) [sort (f a b) | f <- [ pares2 , pares3 , pares4 ]] prop_pares2 :: Integer -> Integer -> Property prop_pares2 a b = a > 0 && b > 0 ==> all (== pares1 a (a * b)) [sort (f a (a * b)) | f <- [ pares2 , pares3 , pares4 ]] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares -- +++ OK, passed 100 tests. -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares -- +++ OK, passed 100 tests. -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares2 -- +++ OK, passed 100 tests. -- 1ª definición de nPares -- ======================= nPares1 :: Integer -> Integer -> Integer nPares1 a b = genericLength (pares4 a b) -- 2ª definición de nPares -- ======================= nPares2 :: Integer -> Integer -> Integer nPares2 a b = 2^(length (nub (primeFactors (b `div` a)))) -- Comparación de eficiencia -- λ> nPares1 3 (product [3,5..91]) -- 8388608 -- (4.68 secs, 4,178,295,920 bytes) -- λ> nPares2 3 (product [3,5..91]) -- 8388608 -- (0.00 secs, 234,688 bytes) -- Propiedad de equivalencia de nPares -- =================================== prop_nPares :: Integer -> Integer -> Property prop_nPares a b = a > 0 && b > 0 ==> nPares1 a (a * b) == nPares2 a (a * b) -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_nPares -- +++ OK, passed 100 tests. |
Pensamiento
Largo es el camino de la enseñanza por medio de teorías; breve y eficaz por medio de ejemplos. ~ Séneca
Si pones el tipo Integer en vez de Int, y genericLength en vez de length te funcionaría para el ejemplo grande