Menu Close

Pares definidos por su MCD y su MCM

José A. Alonso,

Definir las siguientes funciones

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

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]
 
-- Comparacioń 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 pare 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 orde. 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.
Posted in Medio
Tagged , , , , , , , , , , , ,

5 Comments

  1. jaibengue
    Responder

    Una primera idea para ir dándole vueltas:

    import Data.List
import Data.Numbers.Primes
 
pares :: Integer -> Integer -> [(Integer,Integer)]
pares a b
  | b `mod` a /= 0 = []
  | otherwise      = [(a*l, b`div`l)
                     | x <- conjuntoPot(group(primeFactors u))
                     , let l = productoBueno x]
  where u = b `div` a
 
productoBueno :: [[Integer]] -> Integer
productoBueno []     = 1
productoBueno (x:xs) = (head x) ^ (length x) * (productoBueno xs)
 
conjuntoPot :: [a] -> [[a]]
conjuntoPot []     = [[]]
conjuntoPot (x:xs) = u ++ map (x:) u
  where u = conjuntoPot xs
 
nPares :: Integer -> Integer -> Integer
nPares a b
  | b `mod` a /= 0 = 0
  | otherwise      = 2^(length(group(primeFactors(b `div` a))))

    Ahora a mejorarla ^^

    • angruicam1
      Responder

      Buenas, se me ocurre que para mejorar tu función puedes emplear la función subsequences (definida en la librería Data.List) en lugar de definir la función conjuntoPot. De esa forma mejoras la eficiencia de la función.

      Comparación de la eficiencia:

      λ> length (pares 3 (product [3,5..91]))
      8388608
      (6.50 secs, 3,154,333,856 bytes)
      λ> length (pares2 3 (product [3,5..91]))
      8388608
      (4.64 secs, 2,818,784,776 bytes)

      *La función pares es la tuya y la función pares2 es igual pero sustituyendo lo comentado.

      Por lo demás no se me ocurre nada más por el momento para mejorarla.

      • jaibengue
        Responder

        Gracias por tu comentario!

        Por cierto, me he dado cuenta de, en la línea 15:
        conjuntoPot (x:xs) = u ++ map (x:) u
        en lugar de
        conjuntoPot (x:xs) = map (x:) u ++ u
        que es, lo segundo, ligeramente más eficiente.

  2. jaiturrod
    Responder 
    pares :: Integer -> Integer -> [(Integer,Integer)]
pares a b =
  [(x,y) | x <- [a..b]
         , y <-[a..b]
         , gcd x y == a
         , lcm x y == b]
 
nPares :: Integer -> Integer -> Integer
nPares a b = fromIntegral (length (pares a b))
  3. ferquigon
    Responder 
    pares :: Integer -> Integer -> [(Integer,Integer)]
pares a b
  | mod (max a b) (min a b) /= 0 = []
  | otherwise = [(n,m) | n <- [1.. z]
                       , m <- [1.. z]
                       , mcm n m == b
                       , mcd n m == a]
  where z = max a b
 
mcm :: Integer -> Integer -> Integer
mcm c d = minimum [z | z <- [1..(c*d)]
                     , rem z c == 0
                     , rem z d == 0]
 
mcd :: Integer -> Integer -> Integer
mcd c d = maximum [z | z <- [1..(min c d)]
                     , rem c z == 0
                     , rem d z == 0]
 
nPares :: Integer -> Integer -> Integer
nPares a b = length' (pares a b)
 
length' :: [(Integer,Integer)] -> Integer
length' xs = sum [1| _ <- xs]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.