{"id":6617,"date":"2022-02-16T06:00:53","date_gmt":"2022-02-16T04:00:53","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6617"},"modified":"2022-04-15T12:06:37","modified_gmt":"2022-04-15T10:06:37","slug":"numeros-amigos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-amigos\/","title":{"rendered":"N\u00fameros amigos"},"content":{"rendered":"<p>Dos <a href=\"https:\/\/bit.ly\/36gSRHt\">n\u00fameros amigos<\/a> son dos n\u00fameros enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un n\u00famero incluyen la unidad pero no al propio n\u00famero. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos n\u00fameros equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   amigos :: Integer -> Integer -> Bool\n<\/pre>\n<p>tal que (amigos x y) se verifica si los n\u00fameros x e y son amigos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   amigos 220 284 == True\n   amigos 220 23  == False\n   amigos 42262694537514864075544955198125 42405817271188606697466971841875 == True\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group, inits, nub, sort, subsequences)\nimport Data.Numbers.Primes (primeFactors)\n\n-- 1\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos1 :: Integer -> Integer -> Bool\namigos1 x y = sumaDivisoresPropios1 x == y &&\n              sumaDivisoresPropios1 y == x\n\n-- (sumaDivisoresPropios1 x) es la suma de los divisores propios de\n-- x. Por ejemplo,\n--    sumaDivisoresPropios1 220  ==  284\n--    sumaDivisoresPropios1 284  ==  220\nsumaDivisoresPropios1 :: Integer -> Integer\nsumaDivisoresPropios1 = sum . divisoresPropios1\n\n-- (divisoresPropios1 x) es la lista de los divisores propios de x. Por\n-- ejemplo,\n--    divisoresPropios1 220  ==  [1,2,4,5,10,11,20,22,44,55,110]\n--    divisoresPropios1 284  ==  [1,2,4,71,142]\ndivisoresPropios1 :: Integer -> [Integer]\ndivisoresPropios1 x = [n | n <- [1..x-1], x `mod` n == 0]\n\n-- 2\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos2 :: Integer -> Integer -> Bool\namigos2 x y = sumaDivisoresPropios2 x == y &&\n              sumaDivisoresPropios2 y == x\n\nsumaDivisoresPropios2 :: Integer -> Integer\nsumaDivisoresPropios2 = sum . divisoresPropios2\n\ndivisoresPropios2 :: Integer -> [Integer]\ndivisoresPropios2 x = filter ((== 0) . mod x) [1..x-1]\n\n-- 3\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos3 :: Integer -> Integer -> Bool\namigos3 x y = sumaDivisoresPropios3 x == y &&\n              sumaDivisoresPropios3 y == x\n\nsumaDivisoresPropios3 :: Integer -> Integer\nsumaDivisoresPropios3 = sum . divisoresPropios3\n\ndivisoresPropios3 :: Integer -> [Integer]\ndivisoresPropios3 =\n  init . nub . sort . map product . subsequences . primeFactors\n\n-- 4\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos4 :: Integer -> Integer -> Bool\namigos4 x y = sumaDivisoresPropios4 x == y &&\n              sumaDivisoresPropios4 y == x\n\nsumaDivisoresPropios4 :: Integer -> Integer\nsumaDivisoresPropios4 = sum . divisoresPropios4\n\ndivisoresPropios4 :: Integer -> [Integer]\ndivisoresPropios4 =\n  init\n  . sort\n  . map (product . concat)\n  . productoCartesiano\n  . map inits\n  . group\n  . primeFactors\n\n-- (productoCartesiano xss) es el producto cartesiano de los conjuntos\n-- xss. Por ejemplo,\n--    \u03bb> productoCartesiano [[1,3],[2,5],[6,4]]\n--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]\nproductoCartesiano :: [[a]] -> [[a]]\nproductoCartesiano []       = [[]]\nproductoCartesiano (xs:xss) =\n  [x:ys | x <- xs, ys <- productoCartesiano xss]\n\n-- 5\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos5 :: Integer -> Integer -> Bool\namigos5 x y = sumaDivisoresPropios5 x == y &&\n              sumaDivisoresPropios5 y == x\n\nsumaDivisoresPropios5 :: Integer -> Integer\nsumaDivisoresPropios5 =\n  sum . divisoresPropios5\n\ndivisoresPropios5 :: Integer -> [Integer]\ndivisoresPropios5 =\n  init\n  . sort\n  . map (product . concat)\n  . sequence\n  . map inits\n  . group\n  . primeFactors\n\n-- 6\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos6 :: Integer -> Integer -> Bool\namigos6 x y = sumaDivisoresPropios6 x == y &&\n              sumaDivisoresPropios6 y == x\n\nsumaDivisoresPropios6 :: Integer -> Integer\nsumaDivisoresPropios6 =\n  sum\n  . init\n  . map (product . concat)\n  . sequence\n  . map inits\n  . group\n  . primeFactors\n\n-- 7\u00aa soluci\u00f3n                                                   --\n-- ===========\n\namigos7 :: Integer -> Integer -> Bool\namigos7 x y = sumaDivisoresPropios7 x == y &&\n              sumaDivisoresPropios7 y == x\n\n-- Si la descomposici\u00f3n de x en factores primos es\n--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)\n-- entonces la suma de los divisores de x es\n--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1\n--   ------------------- . ------------------- ... -------------------\n--        p(1)-1                p(2)-1                  p(n)-1\n-- Ver la demostraci\u00f3n en http:\/\/bit.ly\/2zUXZPc\n\n-- (sumaDivisoresPropios7 x) es la suma de los divisores propios de\n-- x. Por ejemplo,\n--    sumaDivisoresPropios7 220  ==  284\n--    sumaDivisoresPropios7 284  ==  220\nsumaDivisoresPropios7 :: Integer -> Integer\nsumaDivisoresPropios7 x =\n  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] - x\n\n-- (factorizacion x) es la lista de las bases y exponentes de la\n-- descomposici\u00f3n prima de x. Por ejemplo,\n--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion = map primeroYlongitud . group . primeFactors\n\n-- (primeroYlongitud xs) es el par formado por el primer elemento de xs\n-- y la longitud de xs. Por ejemplo,\n--    primeroYlongitud [3,2,5,7] == (3,4)\nprimeroYlongitud :: [a] -> (a,Integer)\nprimeroYlongitud (x:xs) = (x, 1 + genericLength xs)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> amigos1 2803580 3716164\n--    True\n--    (2.27 secs, 1,304,055,864 bytes)\n--    \u03bb> amigos2 2803580 3716164\n--    True\n--    (0.81 secs, 782,478,584 bytes)\n--    \u03bb> amigos3 2803580 3716164\n--    True\n--    (0.01 secs, 383,888 bytes)\n--    \u03bb> amigos4 2803580 3716164\n--    True\n--    (0.01 secs, 461,376 bytes)\n--    \u03bb> amigos5 2803580 3716164\n--    True\n--    (0.00 secs, 412,560 bytes)\n--    \u03bb> amigos6 2803580 3716164\n--    True\n--    (0.00 secs, 387,816 bytes)\n--    \u03bb> amigos7 2803580 3716164\n--    True\n--    (0.01 secs, 339,008 bytes)\n--\n--    \u03bb> amigos2 5864660 7489324\n--    True\n--    (1.74 secs, 1,602,582,592 bytes)\n--    \u03bb> amigos3 5864660 7489324\n--    True\n--    (0.00 secs, 277,056 bytes)\n--    \u03bb> amigos4 5864660 7489324\n--    True\n--    (0.01 secs, 354,872 bytes)\n--    \u03bb> amigos5 5864660 7489324\n--    True\n--    (0.01 secs, 305,792 bytes)\n--    \u03bb> amigos6 5864660 7489324\n--    True\n--    (0.00 secs, 281,528 bytes)\n--    \u03bb> amigos7 5864660 7489324\n--    True\n--    (0.01 secs, 237,176 bytes)\n--\n--    \u03bb> amigos3 42262694537514864075544955198125 42405817271188606697466971841875\n--    True\n--    (107.54 secs, 5,594,306,392 bytes)\n--    \u03bb> amigos4 42262694537514864075544955198125 42405817271188606697466971841875\n--    True\n--    (1.03 secs, 942,530,824 bytes)\n--    \u03bb> amigos5 42262694537514864075544955198125 42405817271188606697466971841875\n--    True\n--    (0.51 secs, 591,144,304 bytes)\n--    \u03bb> amigos6 42262694537514864075544955198125 42405817271188606697466971841875\n--    True\n--    (0.26 secs, 379,534,608 bytes)\n--    \u03bb> amigos7 42262694537514864075544955198125 42405817271188606697466971841875\n--    True\n--    (0.05 secs, 25,635,464 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numeros_amigos.hs\">GitHub<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dos n\u00fameros amigos son dos n\u00fameros enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un n\u00famero incluyen la unidad pero no al propio n\u00famero. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44,&#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":[2],"tags":[8,498,501,11,521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6617"}],"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=6617"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6617\/revisions"}],"predecessor-version":[{"id":6703,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6617\/revisions\/6703"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6617"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6617"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6617"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}