{"id":3761,"date":"2018-02-22T06:00:12","date_gmt":"2018-02-22T04:00:12","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3761"},"modified":"2022-03-26T10:00:19","modified_gmt":"2022-03-26T08:00:19","slug":"menor-potencia-de-2-que-comienza-por-n","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/menor-potencia-de-2-que-comienza-por-n\/","title":{"rendered":"Menor potencia de 2 que comienza por n"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   menorPotencia            :: Integer -> (Integer,Integer)\n   graficaMenoresExponentes :: Integer -> IO () \n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(menorPotencia n) es el par (k,m) donde m es la menor potencia de 2 que empieza por n y k es su exponentes (es decir, 2^k = m). Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     menorPotencia 3             ==  (5,32)\n     menorPotencia 7             ==  (46,70368744177664)\n     fst (menorPotencia 982)     ==  3973\n     fst (menorPotencia 32627)   ==  28557\n     fst (menorPotencia 158426)  ==  40000\n<\/pre>\n<ul>\n<li>(graficaMenoresExponentes n) dibuja la gr\u00e1fica de los exponentes de 2 en las menores potencias de los n primeros n\u00fameros enteros positivos. Por ejemplo, (graficaMenoresExponentes 200) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Menor_potencia_de_2_que_comienza_por_n.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Menor_potencia_de_2_que_comienza_por_n.png?resize=640%2C480\" alt=\"Menor_potencia_de_2_que_comienza_por_n\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3764\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Menor_potencia_de_2_que_comienza_por_n.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Menor_potencia_de_2_que_comienza_por_n.png?resize=300%2C225&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Menor_potencia_de_2_que_comienza_por_n.png?resize=100%2C75&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Menor_potencia_de_2_que_comienza_por_n.png?resize=150%2C112&amp;ssl=1 150w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List               (isPrefixOf)\nimport Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nmenorPotencia :: Integer -> (Integer,Integer)\nmenorPotencia n =\n  head [(k,m) | (k,m) <- zip [0..] potenciasDe2\n              , cs `isPrefixOf` show m]\n  where cs = show n\n\n-- potenciasDe 2 es la lista de las potencias de dos. Por ejemplo,\n--    take 12 potenciasDe2  ==  [1,2,4,8,16,32,64,128,256,512,1024,2048]\npotenciasDe2 :: [Integer]\npotenciasDe2 = iterate (*2) 1\n\n-- 2\u00aa definici\u00f3n \n-- =============\n\nmenorPotencia2 :: Integer -> (Integer,Integer)\nmenorPotencia2 n = aux (0,1)\n  where aux (k,m) | cs `isPrefixOf` show m = (k,m)\n                  | otherwise              = aux (k+1,2*m)\n        cs = show n\n\n-- 3\u00aa definici\u00f3n \n-- =============\n\nmenorPotencia3 :: Integer -> (Integer,Integer)\nmenorPotencia3 n =\n  until (isPrefixOf n1 . show . snd) (\\(x,y) -> (x+1,2*y)) (0,1)\n  where n1 = show n\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximum [fst (menorPotencia n) | n <- [1..1000]]\n--    3973\n--    (3.69 secs, 1,094,923,696 bytes)\n--    \u03bb> maximum [fst (menorPotencia2 n) | n <- [1..1000]]\n--    3973\n--    (5.13 secs, 1,326,382,872 bytes)\n--    \u03bb> maximum [fst (menorPotencia3 n) | n <- [1..1000]]\n--    3973\n--    (4.71 secs, 1,240,498,128 bytes)\n\ngraficaMenoresExponentes :: Integer -> IO ()\ngraficaMenoresExponentes n =\n  plotList [ Key Nothing\n           , PNG \"Menor_potencia_de_2_que_comienza_por_n.png\"\n           ]\n           (map (fst . menorPotencia) [1..n])\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones menorPotencia :: Integer -> (Integer,Integer) graficaMenoresExponentes :: Integer -> IO () tales que (menorPotencia n) es el par (k,m) donde m es la menor potencia de 2 que empieza por n y k es su exponentes (es decir, 2^k = m). Por ejemplo, menorPotencia 3 == (5,32) menorPotencia 7 == (46,70368744177664) fst&#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":[8,80,376,170,50,415,10,11,309,33,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3761"}],"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=3761"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3761\/revisions"}],"predecessor-version":[{"id":3840,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3761\/revisions\/3840"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3761"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3761"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3761"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}