{"id":8537,"date":"2024-04-14T06:00:05","date_gmt":"2024-04-14T04:00:05","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8537"},"modified":"2024-04-27T19:54:58","modified_gmt":"2024-04-27T17:54:58","slug":"14-abr-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/14-abr-24\/","title":{"rendered":"N\u00fameros amigos"},"content":{"rendered":"<p>Dos <a href=\"https:\/\/bit.ly\/36gSRHt\">n\u00fameros amigos<\/a> son dos n\u00fameros  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,  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=\"haskell\">\n   amigos :: Integer -> Integer -> Bool\n<\/pre>\n<p>tal que <code>amigos x y<\/code> se verifica si los n\u00fameros <code>x<\/code> e <code>y<\/code> son amigos. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   amigos 220 284 == True\n   amigos 220 23  == False\n   amigos 42262694537514864075544955198125 42405817271188606697466971841875 == True\n<\/pre>\n<p><!--more--><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Numeros_amigos where\n\nimport Data.List (genericLength, group, inits, nub, sort, subsequences)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\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-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> Integer -> Bool) -> Spec\nspecG amigos = do\n  it \"e1\" $\n    amigos 220 284 `shouldBe` True\n  it \"e2\" $\n    amigos 220 23  `shouldBe` False\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG amigos1\n  describe \"def. 2\" $ specG amigos2\n  describe \"def. 3\" $ specG amigos3\n  describe \"def. 4\" $ specG amigos4\n  describe \"def. 5\" $ specG amigos5\n  describe \"def. 6\" $ specG amigos6\n  describe \"def. 7\" $ specG amigos7\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--    14 examples, 0 failures\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<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom functools import reduce\nfrom operator import mul\nfrom timeit import Timer, default_timer\n\nfrom sympy import divisor_sigma, factorint, is_amicable, proper_divisors\n\n# 1\u00aa soluci\u00f3n\n# ===========\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]\ndef divisoresPropios1(x: int) -> list[int]:\n    return [n for n in range(1, x) if x % n == 0]\n\n# sumaDivisoresPropios1(x) es la suma de los divisores propios de\n# x. Por ejemplo,\n#    sumaDivisoresPropios1(220)  ==  284\n#    sumaDivisoresPropios1(284)  ==  220\ndef sumaDivisoresPropios1(x: int) -> int:\n    return sum(divisoresPropios1(x))\n\ndef amigos1(x: int, y: int) -> bool:\n    return sumaDivisoresPropios1(x)== y and \\\n           sumaDivisoresPropios1(y)== x\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef divisoresPropios2(x: int) -> list[int]:\n    return proper_divisors(x)\n\ndef sumaDivisoresPropios2(x: int) -> int:\n    return sum(divisoresPropios2(x))\n\ndef amigos2(x: int, y: int) -> bool:\n    return sumaDivisoresPropios2(x)== y and \\\n           sumaDivisoresPropios2(y)== x\n\n# 3\u00aa soluci\u00f3n\n# ===========\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# producto(xs) es el producto de los elementos de xs. Por ejemplo,\n#    producto([2, 3, 5]) == 30\ndef producto(xs: list[int]) -> int:\n    return reduce(mul, xs)\n\n# sumaDivisoresPropios3(x) es la suma de los divisores propios de\n# x. Por ejemplo,\n#    sumaDivisoresPropios3(220)  ==  284\n#    sumaDivisoresPropios3(284)  ==  220\ndef sumaDivisoresPropios3(x: int) -> int:\n    return producto([(p**(e+1)-1) \/\/ (p-1)\n                     for (p,e) in factorint(x).items()]) - x\n\ndef amigos3(x: int, y: int) -> bool:\n    return sumaDivisoresPropios3(x)== y and \\\n           sumaDivisoresPropios3(y)== x\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef amigos4(x: int, y: int) -> bool:\n    return divisor_sigma(x, 1) == divisor_sigma(y, 1)\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef amigos5(x: int, y: int) -> bool:\n    return is_amicable(x, y)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_amigos() -> None:\n    for amigos in [amigos1, amigos2, amigos3, amigos4, amigos5]:\n        assert amigos(220, 284)\n        assert not amigos(220, 23)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_amigos()\n#    Verificado\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('amigos1(5864660, 7489324)')\n#    0.65 segundos\n#    >>> tiempo('amigos2(5864660, 7489324)')\n#    0.00 segundos\n#    >>> tiempo('amigos3(5864660, 7489324)')\n#    0.00 segundos\n#    >>> tiempo('amigos4(5864660, 7489324)')\n#    0.00 segundos\n#    >>> tiempo('amigos5(5864660, 7489324)')\n#    0.00 segundos\n#\n#    >>> x = 42262694537514864075544955198125\n#    >>> y = 42405817271188606697466971841875\n#    >>> tiempo('amigos2(x, y)')\n#    0.10 segundos\n#    >>> tiempo('amigos3(x, y)')\n#    0.00 segundos\n#    >>> tiempo('amigos4(x, y)')\n#    0.00 segundos\n#    >>> tiempo('amigos5(x, y)')\n#    0.00 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Dos n\u00fameros amigos son dos n\u00fameros 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, divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y&#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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8537"}],"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=8537"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8537\/revisions"}],"predecessor-version":[{"id":8539,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8537\/revisions\/8539"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}