{"id":5239,"date":"2019-12-13T05:30:21","date_gmt":"2019-12-13T03:30:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5239"},"modified":"2019-12-20T09:47:02","modified_gmt":"2019-12-20T07:47:02","slug":"pares-definidos-por-su-mcd-y-su-mcm","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/pares-definidos-por-su-mcd-y-su-mcm\/","title":{"rendered":"Pares definidos por su MCD y su MCM"},"content":{"rendered":"<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   pares  :: Integer -> Integer -> [(Integer,Integer)]\n   nPares :: Integer -> Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(pares a b) es la lista de los pares de n\u00fameros enteros positivos tales que su m\u00e1ximo com\u00fan divisor es a y su m\u00ednimo com\u00fan m\u00faltiplo es b. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     pares 3 3  == [(3,3)]\n     pares 4 12 == [(4,12),(12,4)]\n     pares 2 12 == [(2,12),(4,6),(6,4),(12,2)]\n     pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]\n     pares 2 7  == []\n     pares 12 3  ==  []\n     length (pares 3 (product [3,5..91]))  ==  8388608\n<\/pre>\n<ul>\n<li>(nPares a b) es el n\u00famero de pares de enteros positivos tales que su m\u00e1ximo com\u00fan divisor es a y su m\u00ednimo com\u00fan m\u00faltiplo es b. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nPares 3 3   ==  1\n     nPares 4 12  ==  2\n     nPares 2 12  ==  4\n     nPares 2 60  ==  8\n     nPares 2 7   ==  0\n     nPares 12 3  ==  0\n     nPares 3 (product [3..3*10^4]) `mod` (10^12)  ==  477999992832\n     length (show (nPares 3 (product [3..3*10^4])))  ==  977\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primeFactors)\nimport Data.List (genericLength, group, nub, sort, subsequences)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de pares\n-- ======================\n\npares1 :: Integer -> Integer -> [(Integer,Integer)]\npares1 a b = [(x,y) | x <- [1..b]\n                    , y <- [1..b]\n                    , gcd x y == a\n                    , lcm x y == b]\n\n-- 2\u00aa definici\u00f3n de pares\n-- ======================\n\npares2 :: Integer -> Integer -> [(Integer,Integer)]\npares2 a b = [(x,y) | x <- [a,a+a..b]\n                    , y <- [a,a+a..b]\n                    , gcd x y == a\n                    , lcm x y == b]\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> length (pares1 3 (product [3,5..11]))\n--    16\n--    (95.12 secs, 86,534,165,528 bytes)\n--    \u03bb> length (pares2 3 (product [3,5..11]))\n--    16\n--    (15.80 secs, 14,808,762,128 bytes)\n\n-- 3\u00aa definici\u00f3n de pares\n-- ======================\n\npares3 :: Integer -> Integer -> [(Integer,Integer)]\npares3 a b = [(x,y) | x <- [a,a+a..b]\n                    , c `rem` x == 0\n                    , let y = c `div` x\n                    , gcd x y == a\n                    ]\n  where c = a * b\n\n-- Comparacio\u0144 de eficiencia\n--    \u03bb> length (pares2 3 (product [3,5..11]))\n--    16\n--    (15.80 secs, 14,808,762,128 bytes)\n--    \u03bb> length (pares3 3 (product [3,5..11]))\n--    16\n--    (0.01 secs, 878,104 bytes)\n\n-- 4\u00aa definici\u00f3n de pares\n-- ======================\n\n-- Para la cuarta definici\u00f3n de pares se observa la relaci\u00f3n con los\n-- factores primos\n--    \u03bb> [(primeFactors x, primeFactors y) | (x,y) <- pares1 2 12]\n--    [([2],[2,2,3]),([2,2],[2,3]),([2,3],[2,2]),([2,2,3],[2])]\n--    \u03bb> [primeFactors x | (x,y) <- pares1 2 12]\n--    [[2],[2,2],[2,3],[2,2,3]]\n--    \u03bb> [primeFactors x | (x,y) <- pares1 2 60]\n--    [[2],[2,2],[2,3],[2,5],[2,2,3],[2,2,5],[2,3,5],[2,2,3,5]]\n--    \u03bb> [primeFactors x | (x,y) <- pares1 6 60]\n--    [[2,3],[2,2,3],[2,3,5],[2,2,3,5]]\n--    \u03bb> [primeFactors x | (x,y) <- pares1 2 24]\n--    [[2],[2,3],[2,2,2],[2,2,2,3]]\n-- Se observa que cada pares se obtiene de uno de los subconjuntos de los\n-- divisores primos de b\/a. Por ejemplo,\n--    \u03bb> (a,b) = (2,24)\n--    \u03bb> b `div` a\n--    12\n--    \u03bb> primeFactors it\n--    [2,2,3]\n--    \u03bb> group it\n--    [[2,2],[3]]\n--    \u03bb> subsequences it\n--    [[],[[2,2]],[[3]],[[2,2],[3]]]\n--    \u03bb> map concat it\n--    [[],[2,2],[3],[2,2,3]]\n--    \u03bb> map product it\n--    [1,4,3,12]\n--    \u03bb> [(a * x, b `div` x) | x <- it]\n--    [(2,24),(8,6),(6,8),(24,2)]\n-- A partir de la observaci\u00f3n se construye la siguiente definici\u00f3n\n\npares4 :: Integer -> Integer -> [(Integer,Integer)]\npares4 a b\n  | b `mod` a \/= 0 = []\n  | otherwise =\n    [(a * x, b `div` x)\n    | x <- map (product . concat)\n               ((subsequences . group . primeFactors) (b `div` a))]\n\n-- Nota. La funci\u00f3n pares4 calcula el mismo conjunto que las anteriores,\n-- pero no necesariamente en el mismo orden. Por ejemplo,\n--    \u03bb> pares3 2 60 \n--    [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]\n--    \u03bb> pares4 2 60 \n--    [(2,60),(4,30),(6,20),(12,10),(10,12),(20,6),(30,4),(60,2)]\n--    \u03bb> pares3 2 60 == sort (pares4 2 60)\n--    True\n\n-- Comparacio\u0144 de eficiencia\n--    \u03bb> length (pares3 3 (product [3,5..17]))\n--    64\n--    (4.44 secs, 2,389,486,440 bytes)\n--    \u03bb> length (pares4 3 (product [3,5..17]))\n--    64\n--    (0.00 secs, 177,704 bytes)\n  \n-- Propiedades de equivalencia de pares\n-- ====================================\n\nprop_pares :: Integer -> Integer -> Property\nprop_pares a b =\n  a > 0 && b > 0 ==>\n  all (== pares1 a b)\n      [sort (f a b) | f <- [ pares2\n                           , pares3\n                           , pares4\n                           ]]\n  \nprop_pares2 :: Integer -> Integer -> Property\nprop_pares2 a b =\n  a > 0 && b > 0 ==>\n  all (== pares1 a (a * b))\n      [sort (f a (a * b)) | f <- [ pares2\n                                 , pares3\n                                 , pares4\n                                 ]]\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_pares\n--    +++ OK, passed 100 tests.\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_pares\n--    +++ OK, passed 100 tests.\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_pares2\n--    +++ OK, passed 100 tests.\n             \n-- 1\u00aa definici\u00f3n de nPares\n-- =======================\n\nnPares1 :: Integer -> Integer -> Integer\nnPares1 a b = genericLength (pares4 a b)\n\n-- 2\u00aa definici\u00f3n de nPares\n-- =======================\n\nnPares2 :: Integer -> Integer -> Integer\nnPares2 a b = 2^(length (nub (primeFactors (b `div` a))))\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> nPares1 3 (product [3,5..91])\n--    8388608\n--    (4.68 secs, 4,178,295,920 bytes)\n--    \u03bb> nPares2 3 (product [3,5..91])\n--    8388608\n--    (0.00 secs, 234,688 bytes)\n\n-- Propiedad de equivalencia de nPares\n-- ===================================\n\nprop_nPares :: Integer -> Integer -> Property\nprop_nPares a b =\n  a > 0 && b > 0 ==>\n  nPares1 a (a * b) == nPares2 a (a * b)\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_nPares\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nLargo es el camino de la ense\u00f1anza por medio de teor\u00edas; breve y eficaz por medio de ejemplos. ~ S\u00e9neca\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>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\u00fameros enteros positivos tales que su m\u00e1ximo com\u00fan divisor es a y su m\u00ednimo com\u00fan m\u00faltiplo es b. Por ejemplo, pares 3 3 == [(3,3)]&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[8,12,30,155,13,288,10,89,11,247,157,31,88],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5239"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5239"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5239\/revisions"}],"predecessor-version":[{"id":5278,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5239\/revisions\/5278"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5239"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5239"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5239"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}