{"id":6074,"date":"2021-02-19T06:00:25","date_gmt":"2021-02-19T04:00:25","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6074"},"modified":"2021-02-26T12:53:34","modified_gmt":"2021-02-26T10:53:34","slug":"numeros-balanceados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-balanceados\/","title":{"rendered":"N\u00fameros balanceados"},"content":{"rendered":"

Un n\u00famero est\u00e1 balanceado si tiene un n\u00famero par de divisores primos (contados con su multiplicidad). Por ejemplo, 60 es balanceado porque tiene 4 divisores primos (2, 2, 3 y 5).<\/p>\n

Un balanceador del entero positivo k es par de enteros positivos (a,b) tales que a es menor que b y, para todo x entre 1 y k, el valor del polinomio P(x) = (x+a)*(x+b) es un n\u00famero balanceado. Por ejemplo, (2,4) es un balanceador de 3 ya que<\/p>\n

\nP(1) = (1+2)*(1+4) = 15 = 3*5     es balanceado\nP(2) = (2+2)*(2+4) = 24 = 2*2*2*3 es balanceado\nP(3) = (3+2)*(3+4) = 35 = 5*7     es balanceado\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   balanceadores :: Integer -> [(Integer,Integer)]\n<\/pre>\n
tal que (balanceadores k) es el conjunto de los balanceadores de k. Por ejemplo,<\/p>\n
\n   \u03bb> take 7 (balanceadores 3)\n   [(2,4),(1,6),(5,9),(1,11),(6,11),(7,12),(8,14)]\n   \u03bb> take 7 (balanceadores 5)\n   [(8,14),(10,17),(6,18),(12,22),(13,23),(8,24),(14,24)]\n   \u03bb> take 7 (balanceadores 3)\n   [(2,4),(1,6),(5,9),(1,11),(6,11),(7,12),(8,14)]\n   \u03bb> take 7 (balanceadores 4)\n   [(6,11),(8,14),(9,15),(10,17),(6,18),(11,18),(7,19)]\n   \u03bb> take 7 (balanceadores 5)\n   [(8,14),(10,17),(6,18),(12,22),(13,23),(8,24),(14,24)]\n   \u03bb> head (balanceadores 19)\n   (1325,2827)\n<\/pre>\n
Nota<\/strong>: Este ejercicio est\u00e1 basado en el problema N2 de la Olimp\u00edada Internacional de Matem\u00e1ticas (IMO) del 2009<\/a>.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.Numbers.Primes (primeFactors)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nbalanceadores :: Integer -> [(Integer,Integer)]\nbalanceadores k =\n  [(a,b) | (a,b) <- pares\n         , all esBalanceado [(x+a)*(x+b) | x <- [1..k]]]\n\n-- (esBalanceado x) se verifica si x es balanceado. Por ejemplo,\n--    esBalanceado 60  ==  True\n--    esBalanceado 50  ==  False\nesBalanceado :: Integer -> Bool\nesBalanceado = even . length . primeFactors\n\n-- pares el lista de pares de enteros positivos con el primero menor que\n-- el segundo. Por ejemplo,\n--    \u03bb> take 10 pares\n--    [(1,2),(1,3),(2,3),(1,4),(2,4),(3,4),(1,5),(2,5),(3,5),(4,5)]\npares :: [(Integer,Integer)]\npares = [(a,b) | b <- [1..]\n               , a <- [1..b-1]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nbalanceadores2 :: Integer -> [(Integer,Integer)]\nbalanceadores2 1 = balanceadores 1\nbalanceadores2 k =\n  [(a,b) | (a,b) <- balanceadores2 (k-1)\n         , all esBalanceado [(x+a)*(x+b) | x <- [1..k]]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nbalanceadores3 :: Integer -> [(Integer,Integer)]\nbalanceadores3 k =\n  [(a,b) | (a,b) <- pares\n         , and [esBalanceado (x+a) == esBalanceado (x+b) | x <- [1..k]]]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> head (balanceadores 17)\n--    (189,282)\n--    (0.53 secs, 1,227,921,384 bytes)\n--    \u03bb> head (balanceadores2 17)\n--    (189,282)\n--    (0.97 secs, 2,483,869,656 bytes)\n--    \u03bb> head (balanceadores3 17)\n--    (189,282)\n--    (0.36 secs, 983,881,264 bytes)\n<\/pre>\n
Nuevas soluciones<\/h4>\n
    \n
  • En los comentarios se pueden escribir nuevas soluciones.\n
  • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
    Un n\u00famero est\u00e1 balanceado si tiene un n\u00famero par de divisores primos (contados con su multiplicidad). Por ejemplo, 60 es balanceado porque tiene 4 divisores primos (2, 2, 3 y 5). Un balanceador del entero positivo k es par de enteros positivos (a,b) tales que a es menor que b y, para todo x entre…<\/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":[5],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6074"}],"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=6074"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6074\/revisions"}],"predecessor-version":[{"id":6126,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6074\/revisions\/6126"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6074"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6074"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6074"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}