{"id":324,"date":"2014-06-20T07:00:50","date_gmt":"2014-06-20T05:00:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=324"},"modified":"2016-05-01T20:23:55","modified_gmt":"2016-05-01T18:23:55","slug":"mayor-sucesion-del-problema-3n1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/mayor-sucesion-del-problema-3n1\/","title":{"rendered":"Mayor sucesi\u00f3n del problema 3n+1"},"content":{"rendered":"<h4>Enunciado<\/h4>\n<pre lang=\"text\">\n-- La sucesi\u00f3n 3n+1 generada por un n\u00famero entero positivo x es la\n-- sucesi\u00f3n generada por el siguiente algoritmo: Se empieza con el\n-- n\u00famero x. Si x es par, se divide entre 2. Si x es impar, se\n-- multiplica por 3 y se le suma 1. El  proceso se repite con el n\u00famero\n-- obtenido hasta que se alcanza el valor 1. Por ejemplo, la sucesi\u00f3n de\n-- n\u00fameros generadas cuando se empieza en 22 es\n--    22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1\n-- Se ha conjeturado (aunque no demostrado) que este algoritmo siempre\n-- alcanza el 1 empezando en cualquier entero positivo.\n-- \n-- Definir la funci\u00f3n\n--    mayorLongitud :: Integer -> Integer -> Integer\n-- tal que (mayorLongitud i j) es el m\u00e1ximo de las longitudes de las\n-- sucesiones 3n+1 para todos los n\u00fameros comprendidos entre i y j,\n-- ambos inclusives. Por ejemplo,\n--    mayorLongitud   1   10  ==  20\n--    mayorLongitud 100  200  ==  125\n--    mayorLongitud 201  210  ==  89\n--    mayorLongitud 900 1000  ==  174\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayorLongitud1 :: Int -> Int -> Int\nmayorLongitud1 i j = maximum [length (sucesion k) | k <- [i..j]]\n\n-- (sucesion n) es la sucesi\u00f3n 3n+1 generada por n. Por ejemplo, \n--    sucesion 22  ==  [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]\nsucesion :: Int -> [Int]\nsucesion 1 = [1]\nsucesion n | even n    = n : sucesion (n `div` 2)\n           | otherwise = n : sucesion (3*n+1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayorLongitud2 :: Int -> Int -> Int\nmayorLongitud2 i j = maximum [longitud k | k <- [i..j]]\n\n-- (longitud n) es la longitud de la sucesi\u00f3n 3n+1 generada por n. Por\n-- ejemplo, \n--    longitud 22  ==  16\nlongitud :: Int -> Int\nlongitud 1 = 1\nlongitud n | even n    = 1 + longitud (n `div` 2)\n           | otherwise = 1 + longitud (3*n+1)\n\n-- 3\u00aa soluci\u00f3n (con iterate)\n-- =========================\n\nmayorLongitud3 :: Int -> Int -> Int\nmayorLongitud3 i j = maximum [length (sucesion2 k) | k <- [i..j]]\n\n-- (sucesion2 n) es la sucesi\u00f3n 3n+1 generada por n. Por ejemplo, \n--    sucesion2 22  ==  [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]\nsucesion2 :: Int -> [Int]\nsucesion2 n = takeWhile (\/=1) (iterate f n) ++ [1]\n    where f x | even x    = x `div` 2\n              | otherwise = 3*x+1\n<\/pre>\n<h4>Referencia<\/h4>\n<p>El ejercicio est\u00e1 basado en <a href=\"http:\/\/bit.ly\/SIcT1Q\">The 3n + 1 problem<\/a> de <a href=\"http:\/\/uva.onlinejudge.org\">UVa Online Judge<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Enunciado &#8212; La sucesi\u00f3n 3n+1 generada por un n\u00famero entero positivo x es la &#8212; sucesi\u00f3n generada por el siguiente algoritmo: Se empieza con el &#8212; n\u00famero x. Si x es par, se divide entre 2. Si x es impar, se &#8212; multiplica por 3 y se le suma 1. El proceso se repite 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":[5],"tags":[8,30,91,50,28,15,11,6,34],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/324"}],"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=324"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/324\/revisions"}],"predecessor-version":[{"id":685,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/324\/revisions\/685"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=324"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=324"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=324"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}