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. |
José A. Alonso