{"id":2611,"date":"2016-11-24T06:00:45","date_gmt":"2016-11-24T04:00:45","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2611"},"modified":"2016-12-01T07:22:30","modified_gmt":"2016-12-01T05:22:30","slug":"menor-potencia-de-2-comenzando-un-numero-dado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/menor-potencia-de-2-comenzando-un-numero-dado\/","title":{"rendered":"Menor potencia de 2 comenzando un n\u00famero dado"},"content":{"rendered":"<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   potenciasDe2  :: Integer -> [Integer]\n   menorPotenciaDe2 :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 5 (potenciasDe2 3)\n     [32,32768,33554432,34359738368,35184372088832]\n     \u03bb> take 2 (potenciasDe2 102)\n     [1024,102844034832575377634685573909834406561420991602098741459288064]\n<\/pre>\n<ul>\n<li>(menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el n\u00famero a. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> menorPotenciaDe2 10\n     1024\n     \u03bb> menorPotenciaDe2 25\n     256\n     \u03bb> menorPotenciaDe2 62\n     6277101735386680763835789423207666416102355444464034512896\n     \u03bb> menorPotenciaDe2 425\n     42535295865117307932921825928971026432\n     \u03bb> menorPotenciaDe2 967140655691\n     9671406556917033397649408\n     \u03bb> [menorPotenciaDe2 a | a <- [1..10]]\n     [1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]\n<\/pre>\n<p>Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (isPrefixOf)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de potenciasDe2\n-- =============================\n\npotenciasDe2A :: Integer -> [Integer]\npotenciasDe2A a =\n  [x | x <- potenciasA\n     , a `esPrefijo` x]\n\npotenciasA :: [Integer]\npotenciasA = [2^n | n <- [0..]]\n\nesPrefijo :: Integer -> Integer -> Bool\nesPrefijo x y = show x `isPrefixOf` show y\n\n-- 2\u00aa definici\u00f3n de potenciasDe2\n-- =============================\n\npotenciasDe2B :: Integer -> [Integer]\npotenciasDe2B a = filter (a `esPrefijo`) potenciasA\n\n-- 3\u00aa definici\u00f3n de potenciasDe2\n-- =============================\n\npotenciasDe2C :: Integer -> [Integer]\npotenciasDe2C a = filter (a `esPrefijo`) potenciasC\n\npotenciasC :: [Integer]\npotenciasC = iterate (*2) 1\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> length (show (head (potenciasDe2A 123456)))\n-- 19054\n-- (7.17 secs, 1,591,992,792 bytes)\n-- \u03bb> length (show (head (potenciasDe2B 123456)))\n-- 19054\n-- (5.96 secs, 1,273,295,272 bytes)\n-- \u03bb> length (show (head (potenciasDe2C 123456)))\n-- 19054\n-- (6.24 secs, 1,542,698,392 bytes)\n\n-- Definici\u00f3n de menorPotenciaDe2 \nmenorPotenciaDe2 :: Integer -> Integer\nmenorPotenciaDe2 = head . potenciasDe2B\n\n-- Propiedad\nprop_potenciasDe2 :: Integer -> Property\nprop_potenciasDe2 a =\n  a > 0 ==> not (null (potenciasDe2B a))\n\n-- Comprobaci\u00f3n\n--    \u03bb> quickCheck prop_potenciasDe2\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Referencias<\/h4>\n<ul>\n<li><a href=\"http:\/\/mathafou.free.fr\/pba_en\/sol042.html\">Potencias de 2<\/a> por Philippe Chevanne en \"Mad Maths\".<\/li>\n<li><a href=\"https:\/\/oeis.org\/A018802\">Sucesi\u00f3n A018802 de la OEIS<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Definir las siguientes funciones potenciasDe2 :: Integer -> [Integer] menorPotenciaDe2 :: Integer -> Integer tales que (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo, \u03bb> take 5 (potenciasDe2 3) [32,32768,33554432,34359738368,35184372088832] \u03bb> take 2 (potenciasDe2 102) [1024,102844034832575377634685573909834406561420991602098741459288064] (menorPotenciaDe2 a) es la menor potencia de 2 que comienza con&#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":[7],"tags":[8,38,170,50,11,33],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2611"}],"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=2611"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2611\/revisions"}],"predecessor-version":[{"id":2646,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2611\/revisions\/2646"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}