{"id":6046,"date":"2021-02-10T06:00:04","date_gmt":"2021-02-10T04:00:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6046"},"modified":"2021-02-17T09:29:17","modified_gmt":"2021-02-17T07:29:17","slug":"ternas-potencias-de-dos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/ternas-potencias-de-dos\/","title":{"rendered":"Ternas potencias de dos"},"content":{"rendered":"<p>Una terna (a,b,c) de n\u00fameros enteros positivos es especial si se verifica que ab-c, bc-a y ca-b son potencias de 2. Por ejemplo, (3,5,7) es especial ya que<\/p>\n<pre lang=\"text\">\n   3 * 5 - 7 =  8 = 2^3\n   5 * 7 - 3 = 32 = 2^5\n   7 * 3 - 5 = 16 = 2^4\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   esEspecial       :: (Integer,Integer,Integer) -> Bool\n   ternasEspeciales :: [(Integer,Integer,Integer)]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esEspecial t) se verifica si t es una terna especial. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     esEspecial (3,5,7)  ==  True\n     esEspecial (5,7,9)  ==  False\n<\/pre>\n<ul>\n<li>ternasEspeciales es la lista de las ternasEspeciales ordenadas seg\u00fan su suma y las de la misma suma por orden lexicogr\u00e1fico. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 16 ternasEspeciales\n     [(2,2,2),\n      (2,2,3),(2,3,2),(3,2,2),\n      (3,5,7),(3,7,5),(5,3,7),(5,7,3),(7,3,5),(7,5,3),\n      (2,6,11),(2,11,6),(6,2,11),(6,11,2),(11,2,6),(11,6,2)]\n<\/pre>\n<p>Comprobar con QuickCheck que s\u00f3lo hay 16 ternas especiales; es decir, para toda terna t de enteros positivos, t pertenece a la lista de los 16 primeros elementos de ternasEspeciales o no es una terna especial.<\/p>\n<p><strong>Nota<\/strong>: Este ejercicio est\u00e1 basado en el problema N5 de la <a href=\"https:\/\/bit.ly\/3rcr4gw\">Olimp\u00edada Internacional de Matem\u00e1ticas (IMO) del 2015<\/a>.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub, permutations, sort)\nimport Data.Numbers.Primes (primeFactors)\nimport Data.Bits ((.&.))\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\n-- 1\u00aa definici\u00f3n de esEspecial\n-- ===========================\n\nesEspecial1 :: (Integer,Integer,Integer) -> Bool\nesEspecial1 (a,b,c) =\n  all esPotenciaDeDos1 [a * b - c, b * c - a, c * a - b]\n\n-- (esPotenciaDeDos n) se verifica si n es una potencia de dos. Por\n-- ejemplo.\n--    esPotenciaDeDos  8  == True\n--    esPotenciaDeDos 32  == True\n--    esPotenciaDeDos  0  == False\n--    esPotenciaDeDos  1  == True\n--    esPotenciaDeDos  2  == True\n--    esPotenciaDeDos  6  == False\nesPotenciaDeDos1 :: Integer -> Bool\nesPotenciaDeDos1 n\n    | n <= 0    = False\n    | n <= 2    = True\n    | even n    = esPotenciaDeDos1 (n `div` 2)\n    | otherwise = False\n\n-- 2\u00aa definici\u00f3n de esEspecial\n-- ===========================\n\nesEspecial2 :: (Integer,Integer,Integer) -> Bool\nesEspecial2 (a,b,c) =\n  all esPotenciaDeDos2 [a * b - c, b * c - a, c * a - b]\n\nesPotenciaDeDos2 :: Integer -> Bool\nesPotenciaDeDos2 n = n == head (dropWhile (<n) potenciasDeDos)\n\n-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,\npotenciasDeDos :: [Integer]\npotenciasDeDos = iterate (*2) 1\n\n-- 3\u00aa definici\u00f3n de esEspecial\n-- ===========================\n\nesEspecial3 :: (Integer,Integer,Integer) -> Bool\nesEspecial3 (a,b,c) =\n  all esPotenciaDeDos3 [a * b - c, b * c - a, c * a - b]\n\nesPotenciaDeDos3 :: Integer -> Bool\nesPotenciaDeDos3 x = all (==2) (primeFactors x)\n\n-- 4\u00aa definici\u00f3n de esEspecial\n-- ===========================\n\nesEspecial4 :: (Integer,Integer,Integer) -> Bool\nesEspecial4 (a,b,c) =\n  all esPotenciaDeDos4 [a * b - c, b * c - a, c * a - b]\n\n-- La siguiente definici\u00f3n de esPotenciaDeDos usa la funci\u00f3n (.&.) de la\n-- librer\u00eda Data.Bits. Dicha funci\u00f3n calcula el n\u00famero correspondiente a\n-- la conjunci\u00f3n de las representaciones binarias de sus argumentos. Por\n-- ejemplo,\n--    6 .&. 3 == 2\n-- ya que\n--    la representaci\u00f3n binaria de 6 es     [1,1,0]\n--    la representaci\u00f3n binaria de 3 es       [1,1]\n--    la conjunci\u00f3n es                        [1,0]\n--    la representaci\u00f3n decimal de [1,0] es   2\n--\n-- Otros ejemplos:\n--    4 .&. 3 ==   [1,0,0] .&.   [1,1] == 0\n--    8 .&. 7 == [1,0,0,0] .&. [1,1,1] = 0\nesPotenciaDeDos4 :: Integer -> Bool\nesPotenciaDeDos4 n = n .&. (n-1) == 0\n\n-- Comparaci\u00f3n de eficiencia de las definiciones de esEspecial\n-- ===========================================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> esEspecial1 (2^300000,2,0)\n--    False\n--    (3.05 secs, 5,765,728,296 bytes)\n--    \u03bb> esEspecial2 (2^300000,2,0)\n--    False\n--    (2.68 secs, 5,755,293,608 bytes)\n--    \u03bb> esEspecial3 (2^300000,2,0)\n--    False\n--    (2.45 secs, 5,758,527,232 bytes)\n--    \u03bb> esEspecial4 (2^300000,2,0)\n--    False\n--    (0.01 secs, 516,512 bytes)\n\n-- Definici\u00f3n de esEspecial\n-- ========================\n\n-- En lo sucesivo usaremos la 4\u00aa definici\u00f3n.\nesEspecial :: (Integer,Integer,Integer) -> Bool\nesEspecial = esEspecial4\n\n-- Definici\u00f3n de ternasEspeciales\n-- ==============================\n\n--    \u03bb> take 16 ternasEspeciales\n--    [(2,2,2),(2,2,3),(2,3,2),(3,2,2),(3,5,7),(3,7,5),(5,3,7),(5,7,3),\n--     (7,3,5),(7,5,3),(2,6,11),(2,11,6),(6,2,11),(6,11,2),(11,2,6),(11,6,2)]\nternasEspeciales :: [(Integer,Integer,Integer)]\nternasEspeciales = filter esEspecial1 ternas\n\n-- ternas es la lista de ternas de enteros positivos con el orden\n-- descrito anteriormente. Por ejemplo,\n--    \u03bb> take 20 ternas\n--    [(1,1,1),\n--     (1,1,2),(1,2,1),(2,1,1),\n--     (1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1),\n--     (1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)]\nternas :: [(Integer,Integer,Integer)]\nternas = concatMap ternasSuma [3..]\n\n-- (ternasSuma n) es la lista de las ternas de enteros positivos cuya\n-- suma es n ordenadas lexicogr\u00e1ficamte. Por ejemplo,\n--    \u03bb> ternasSuma 3\n--    [(1,1,1)]\n--    \u03bb> ternasSuma 4\n--    [(1,1,2),(1,2,1),(2,1,1)]\n--    \u03bb> ternasSuma 5\n--    [(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)]\n--    \u03bb> ternasSuma 6\n--    [(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)]\nternasSuma :: Integer -> [(Integer,Integer,Integer)]\nternasSuma n =\n  sort (concatMap permutaciones [(a,b,c) | a <- [1..n]\n                                         , b <- [a..n]\n                                         , let c = n-a-b\n                                         , b <= c])\n\n\n-- (permutaciones t) es la lista de las permutaciones de la terna t. Por ejemplo,\n--    \u03bb> permutaciones (1,2,3)\n--    [(1,2,3),(2,1,3),(3,2,1),(2,3,1),(3,1,2),(1,3,2)]\n--    \u03bb> permutaciones (1,1,2)\n--    [(1,1,2),(2,1,1),(1,2,1)]\n--    \u03bb> permutaciones (1,1,1)\n--    [(1,1,1)]\npermutaciones :: (Integer,Integer,Integer) -> [(Integer,Integer,Integer)]\npermutaciones (a,b,c) =\n  nub [(x,y,z) | [x,y,z] <- permutations [a,b,c]]\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_ternasEspeciales :: (Integer,Integer,Integer) -> Property\nprop_ternasEspeciales (a,b,c) =\n  a > 0 && b > 0 && c > 0 ==>\n  (a,b,c) `elem` xs || not (esEspecial (a,b,c))\n  where xs = take 16 ternasEspeciales\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ternasEspeciales\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Una terna (a,b,c) de n\u00fameros enteros positivos es especial si se verifica que ab-c, bc-a y ca-b son potencias de 2. Por ejemplo, (3,5,7) es especial ya que 3 * 5 &#8211; 7 = 8 = 2^3 5 * 7 &#8211; 3 = 32 = 2^5 7 * 3 &#8211; 5 = 16 = 2^4&#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":[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\/6046"}],"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=6046"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6046\/revisions"}],"predecessor-version":[{"id":6089,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6046\/revisions\/6089"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}