{"id":2428,"date":"2016-05-10T06:16:21","date_gmt":"2016-05-10T04:16:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2428"},"modified":"2021-04-25T16:26:57","modified_gmt":"2021-04-25T14:26:57","slug":"sucesion-fractal-16","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sucesion-fractal-16\/","title":{"rendered":"Sucesi\u00f3n fractal"},"content":{"rendered":"<p>La <strong>sucesi\u00f3n fractal<\/strong><\/p>\n<pre lang=\"text\">\n   0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, \n   10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...\n<\/pre>\n<p>est\u00e1 construida de la siguiente forma:<\/p>\n<ul>\n<li>los t\u00e9rminos pares forman la sucesi\u00f3n de los n\u00fameros naturales <\/li>\n<\/ul>\n<pre lang=\"text\">\n     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...\n<\/pre>\n<ul>\n<li>los t\u00e9rminos impares forman la misma sucesi\u00f3n original<\/li>\n<\/ul>\n<pre lang=\"text\">\n     0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   sucFractal     :: [Integer]\n   sumaSucFractal :: Integer -> Integer \n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>sucFractal es la lista de los t\u00e9rminos de la sucesi\u00f3n fractal. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]\n     sucFractal !! 30     == 15\n     sucFractal !! (10^7) == 5000000\n<\/pre>\n<ul>\n<li>(sumaSucFractal n) es la suma de los n primeros t\u00e9rminos de la sucesi\u00f3n fractal. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     sumaSucFractal 10      ==  13\n     sumaSucFractal (10^5)  == 1666617368\n     sumaSucFractal (10^10) == 16666666661668691669\n     sumaSucFractal (10^15) == 166666666666666166673722792954\n     sumaSucFractal (10^20) == 1666666666666666666616666684103392376198\n     length (show (sumaSucFractal (10^15000))) == 30000\n     sumaSucFractal (10^15000) `mod` (10^9)    == 455972157\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa definici\u00f3n de sucFractal\n-- ===========================\n\nsucFractal1 :: [Integer]\nsucFractal1 = \n    map termino [0..]\n\n-- (termino n) es el t\u00e9rmino n de la secuencia anterior. Por ejemplo,\n--   termino 0            ==  0\n--   termino 1            ==  0\n--   map termino [0..10]  ==  [0,0,1,0,2,1,3,0,4,2,5]\ntermino :: Integer -> Integer\ntermino 0 = 0\ntermino n \n    | even n    = n `div` 2\n    | otherwise = termino (n `div` 2)\n\n-- 2\u00aa definici\u00f3n de sucFractal\n-- ===========================\n\nsucFractal2 :: [Integer]\nsucFractal2 =\n    0 : 0 : mezcla [1..] (tail sucFractal2)\n\n-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas\n-- xs e ys. Por ejemplo,\n--    take 10 (mezcla [0,2..] [0,-2..])  ==  [0,0,2,-2,4,-4,6,-6,8,-8]\nmezcla :: [Integer] -> [Integer] -> [Integer]\nmezcla (x:xs) (y:ys) =\n    x:y:mezcla xs ys\n\n-- Comparaci\u00f3n de eficiencia de definiciones de sucFractal\n-- =======================================================\n\n--    \u03bb> sum (take (10^6) sucFractal1)\n--    166666169612\n--    (5.56 secs, 842,863,264 bytes)\n--    \u03bb> sum (take (10^6) sucFractal2)\n--    166666169612\n--    (1.81 secs, 306,262,616 bytes)\n\n-- En lo que sigue usaremos la 2\u00aa definici\u00f3n\nsucFractal :: [Integer]\nsucFractal = sucFractal2\n\n-- 1\u00aa definici\u00f3n de sumaSucFractal\n-- ===============================\n\nsumaSucFractal1 :: Integer -> Integer\nsumaSucFractal1 n =\n    sum (map termino [0..n-1])\n\n-- 2\u00aa definici\u00f3n de sumaSucFractal\n-- ===============================\n\nsumaSucFractal2 :: Integer -> Integer\nsumaSucFractal2 n =\n    sum (take (fromIntegral n) sucFractal)\n\n-- 3\u00aa definici\u00f3n de sumaSucFractal\n-- ===============================\n\nsumaSucFractal3 :: Integer -> Integer\nsumaSucFractal3 0 = 0\nsumaSucFractal3 1 = 0\nsumaSucFractal3 n\n    | even n    = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)\n    | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)\n    where sumaN n = (n*(n-1)) `div` 2\n\n-- Comparaci\u00f3n de eficiencia de definiciones de sumaSucFractal\n-- ===========================================================\n\n--    \u03bb> sumaSucFractal1 (10^6)\n--    166666169612\n--    (5.25 secs, 810,622,504 bytes)\n--    \u03bb> sumaSucFractal2 (10^6)\n--    166666169612\n--    (1.72 secs, 286,444,048 bytes)\n--    \u03bb> sumaSucFractal3 (10^6)\n--    166666169612\n--    (0.01 secs, 0 bytes)\n--    \n--    \u03bb> sumaSucFractal2 (10^7)\n--    16666661685034\n--    (17.49 secs, 3,021,580,920 bytes)\n--    \u03bb> sumaSucFractal3 (10^7)\n--    16666661685034\n--    (0.01 secs, 0 bytes)\n<\/pre>\n<h4>Referencia<\/h4>\n<ul>\n<li><a href=\"http:\/\/bit.ly\/1WX1IjB\">Fractal sequences and restricted Nim<\/a> por Lionel Levine.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>La sucesi\u00f3n fractal 0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, &#8230; est\u00e1 construida de la siguiente forma: los t\u00e9rminos pares forman la sucesi\u00f3n de los n\u00fameros naturales 0, 1, 2, 3,&#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":[286,30,91,10,11,6,40,45],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2428"}],"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=2428"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2428\/revisions"}],"predecessor-version":[{"id":2453,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2428\/revisions\/2453"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}