{"id":7155,"date":"2022-07-27T06:00:27","date_gmt":"2022-07-27T04:00:27","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7155"},"modified":"2022-07-20T13:45:46","modified_gmt":"2022-07-20T11:45:46","slug":"la-serie-de-thue-morse","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/la-serie-de-thue-morse\/","title":{"rendered":"La serie de Thue-Morse"},"content":{"rendered":"<p>La <a href=\"http:\/\/bit.ly\/1KvZONW\">serie de Thue-Morse<\/a> comienza con el t\u00e9rmino [0] y sus siguientes t\u00e9rminos se construyen a\u00f1adi\u00e9ndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros t\u00e9rminos de la serie son<\/p>\n<pre lang=\"text\">\n   [0]\n   [0,1]\n   [0,1,1,0]\n   [0,1,1,0,1,0,0,1]\n   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\n<\/pre>\n<p>Definir la lista<\/p>\n<pre lang=\"text\">\n   serieThueMorse :: [[Int]]\n<\/pre>\n<p>tal que sus elementos son los t\u00e9rminos de la serie de Thue-Morse. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 4 serieThueMorse\n   [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse1 :: [[Int]]\nserieThueMorse1 = map termSerieThueMorse [0..]\n\n-- (termSerieThueMorse n) es el t\u00e9rmino n-\u00e9simo de la serie de\n-- Thue-Morse. Por ejemplo, \n--    termSerieThueMorse 1  ==  [0,1]\n--    termSerieThueMorse 2  ==  [0,1,1,0]\n--    termSerieThueMorse 3  ==  [0,1,1,0,1,0,0,1]\n--    termSerieThueMorse 4  ==  [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\ntermSerieThueMorse :: Int -> [Int]\ntermSerieThueMorse 0 = [0]\ntermSerieThueMorse n = xs ++ complementaria xs\n  where xs = termSerieThueMorse (n-1)\n\n-- (complementaria xs) es la complementaria de la lista xs (formada por\n-- ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el\n-- 1 por 0. Por ejemplo, \n--    complementaria [1,0,0,1,1,0,1]  ==  [0,1,1,0,0,1,0]\ncomplementaria :: [Int] -> [Int]\ncomplementaria = map (1-)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse2 :: [[Int]]\nserieThueMorse2 = [0] : map paso serieThueMorse2\n  where paso xs = xs ++ complementaria xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse3 :: [[Int]]\nserieThueMorse3 = iterate paso [0]\n  where paso xs = xs ++ complementaria xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Observando que cada t\u00e9rmino de la serie de Thue-Morse se obtiene del\n-- anterior sustituyendo los 1 por 1, 0 y los 0 por  0, 1. \n\nserieThueMorse4 :: [[Int]]\nserieThueMorse4 = [0] : map (concatMap paso4) serieThueMorse4\n  where paso4 x = [x,1-x]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_serieThueMorse :: NonNegative Int -> Bool \nprop_serieThueMorse  (NonNegative n) =\n  all (== serieThueMorse1 !! n)\n      [serieThueMorse2 !! n,\n       serieThueMorse3 !! n,\n       serieThueMorse4 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_serieThueMorse\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> (serieThueMorse1 !! 23) !! (2^22)\n--    1\n--    (1.08 secs, 839,419,224 bytes)\n--    \u03bb> (serieThueMorse2 !! 23) !! (2^22)\n--    1\n--    (0.61 secs, 839,413,592 bytes)\n--    \u03bb> (serieThueMorse3 !! 23) !! (2^22)\n--    1\n--    (1.43 secs, 839,413,592 bytes)\n--    \u03bb> (serieThueMorse4 !! 23) !! (2^22)\n--    1\n--    (1.57 secs, 1,007,190,024 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/<\/p>\n<h4>Referencias<\/h4>\n<ul>\n<li>N.J.A. Sloane <a href=\"http:\/\/oeis.org\/A010060\">Sucesi\u00f3n A010060 en OEIS<\/a>.<\/li>\n<li>Programming Praxis <a href=\"http:\/\/bit.ly\/1n2PdFk\">Thue-Morse sequence<\/a>.<\/li>\n<li>Wikipedia <a href=\"http:\/\/bit.ly\/1KvZONW\">Thue\u2013Morse sequence<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>La serie de Thue-Morse comienza con el t\u00e9rmino [0] y sus siguientes t\u00e9rminos se construyen a\u00f1adi\u00e9ndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros t\u00e9rminos de la serie son [0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] Definir la lista serieThueMorse :: [[Int]] tal que&#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":[2],"tags":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7155"}],"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=7155"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7155\/revisions"}],"predecessor-version":[{"id":7157,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7155\/revisions\/7157"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7155"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7155"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}