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. Los primeros t\u00e9rminos de la serie son<\/p>\n
\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>\nDe esta forma se va formando una sucesi\u00f3n<\/p>\n
\n 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...\n<\/pre>\nque se conoce como la sucesi\u00f3n de Thue-Morse<\/a>.<\/p>\nDefinir la sucesi\u00f3n<\/p>\n
\n sucThueMorse :: [Int]\n<\/pre>\ncuyos elementos son los de la sucesi\u00f3n de Thue-Morse. Por ejemplo,<\/p>\n
\n \u03bb> take 30 sucThueMorse\n [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]\n \u03bb> map (sucThueMorse4 !!) [1234567..1234596]\n [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0]\n \u03bb> map (sucThueMorse4 !!) [4000000..4000030]\n [1,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]\n<\/pre>\nComprobar con QuickCheck que si s(n) representa el t\u00e9rmino n-\u00e9simo de la sucesi\u00f3n de Thue-Morse, entonces<\/p>\n
\n s(2n) = s(n)\n s(2n+1) = 1 - s(n)\n<\/pre>\n<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n<\/a>
\nSoluciones en Haskell<\/b><\/p>\n\nmodule La_sucesion_de_Thue_Morse where\n\nimport Test.QuickCheck\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse1 :: [Int]\nsucThueMorse1 = map termSucThueMorse1 [0..]\n\n-- (termSucThueMorse1 n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n-- Thue-Morse. Por ejemplo,\n-- termSucThueMorse1 0 == 0\n-- termSucThueMorse1 1 == 1\n-- termSucThueMorse1 2 == 1\n-- termSucThueMorse1 3 == 0\n-- termSucThueMorse1 4 == 1\ntermSucThueMorse1 :: Int -> Int\ntermSucThueMorse1 0 = 0\ntermSucThueMorse1 n =\n (serieThueMorse !! k) !! n\n where k = 1 + floor (logBase 2 (fromIntegral n))\n\n-- serieThueMorse es la lista cuyos elementos son los t\u00e9rminos de la\n-- serie de Thue-Morse. Por ejemplo,\n-- \u03bb> take 4 serieThueMorse3\n-- [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]\nserieThueMorse :: [[Int]]\nserieThueMorse = iterate paso [0]\n where paso xs = xs ++ map (1-) xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse2 :: [Int]\nsucThueMorse2 =\n 0 : intercala (map (1-) sucThueMorse2) (tail sucThueMorse2)\n\n-- (intercala xs ys) es la lista obtenida intercalando los elementos de\n-- las listas infinitas xs e ys. Por ejemplo,\n-- take 10 (intercala [1,5..] [2,4..]) == [1,2,5,4,9,6,13,8,17,10]\nintercala :: [a] -> [a] -> [a]\nintercala (x:xs) ys = x : intercala ys xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse3 :: [Int]\nsucThueMorse3 = 0 : 1 : aux (tail sucThueMorse3)\n where aux (x : xs) = x : (1 - x) : aux xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse4 :: [Int]\nsucThueMorse4 = 0 : aux [1]\n where aux xs = xs ++ aux (xs ++ map (1-) xs)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_termSucThueMorse :: NonNegative Int -> Bool\nprop_termSucThueMorse (NonNegative n) =\n sucThueMorse1 !! (2*n) == sn &&\n sucThueMorse1 !! (2*n+1) == 1 - sn\n where sn = sucThueMorse1 !! n\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_termSucThueMorse\n-- +++ OK, passed 100 tests.\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nsucThueMorse5 :: [Int]\nsucThueMorse5 = map termSucThueMorse5 [0..]\n\n-- (termSucThueMorse5 n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n-- Thue-Morse. Por ejemplo,\n-- termSucThueMorse5 0 == 0\n-- termSucThueMorse5 1 == 1\n-- termSucThueMorse5 2 == 1\n-- termSucThueMorse5 3 == 0\n-- termSucThueMorse5 4 == 1\ntermSucThueMorse5 :: Int -> Int\ntermSucThueMorse5 0 = 0\ntermSucThueMorse5 n\n | even n = termSucThueMorse5 (n `div` 2)\n | otherwise = 1 - termSucThueMorse5 (n `div` 2)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: [Int] -> Spec\nspecG sucThueMorse = do\n it \"e1\" $\n take 30 sucThueMorse `shouldBe`\n [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]\n\nspec :: Spec\nspec = do\n describe \"def. 1\" $ specG sucThueMorse1\n describe \"def. 2\" $ specG sucThueMorse2\n describe \"def. 3\" $ specG sucThueMorse3\n describe \"def. 4\" $ specG sucThueMorse4\n describe \"def. 5\" $ specG sucThueMorse5\n\n-- La verificaci\u00f3n es\n-- \u03bb> verifica\n--\n-- 5 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sucThueMorse :: NonNegative Int -> Bool\nprop_sucThueMorse (NonNegative n) =\n all (== sucThueMorse1 !! n)\n [sucThueMorse2 !! n,\n sucThueMorse3 !! n,\n sucThueMorse4 !! n,\n sucThueMorse5 !! n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_sucThueMorse\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> sucThueMorse1 !! (10^7)\n-- 0\n-- (3.28 secs, 3,420,080,168 bytes)\n-- \u03bb> sucThueMorse2 !! (10^7)\n-- 0\n-- (3.01 secs, 1,720,549,640 bytes)\n-- \u03bb> sucThueMorse3 !! (10^7)\n-- 0\n-- (1.80 secs, 1,360,550,040 bytes)\n-- \u03bb> sucThueMorse4 !! (10^7)\n-- 0\n-- (0.88 secs, 1,254,772,768 bytes)\n-- \u03bb> sucThueMorse5 !! (10^7)\n-- 0\n-- (0.62 secs, 1,600,557,072 bytes)\n<\/pre>\n<\/a>
\nSoluciones en Python<\/b><\/p>\n\nfrom itertools import count, islice\nfrom math import floor, log2\nfrom timeit import Timer, default_timer\nfrom typing import Iterator, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.La_serie_de_Thue_Morse import serieThueMorse\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# nth(i, n) es el n-\u00e9simo elemento del iterador i.\ndef nth(i: Iterator[A], n: int) -> A:\n return list(islice(i, n, n+1))[0]\n\n# termSucThueMorse(n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n# Thue-Morse. Por ejemplo,\n# termSucThueMorse(0) == 0\n# termSucThueMorse(1) == 1\n# termSucThueMorse(2) == 1\n# termSucThueMorse(3) == 0\n# termSucThueMorse(4) == 1\ndef termSucThueMorse(n: int) -> int:\n if n == 0:\n return 0\n k = 1 + floor(log2(n))\n return nth(serieThueMorse(), k)[n]\n\ndef sucThueMorse() -> Iterator[int]:\n return (termSucThueMorse(n) for n in count())\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=100))\ndef test_prop_termSucThueMorse(n: int) -> None:\n sn = nth(sucThueMorse(), n)\n assert nth(sucThueMorse(), 2*n) == sn\n assert nth(sucThueMorse(), 2*n+1) == 1 - sn\n\n# La comprobaci\u00f3n es\n# >>> test_prop_termSucThueMorse()\n# >>>\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# termSucThueMorse2(n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n# Thue-Morse. Por ejemplo,\n# termSucThueMorse2(0) == 0\n# termSucThueMorse2(1) == 1\n# termSucThueMorse2(2) == 1\n# termSucThueMorse2(3) == 0\n# termSucThueMorse2(4) == 1\ndef termSucThueMorse2(n: int) -> int:\n if n == 0:\n return 0\n if n % 2 == 0:\n return termSucThueMorse2(n \/\/ 2)\n return 1 - termSucThueMorse2(n \/\/ 2)\n\ndef sucThueMorse2() -> Iterator[int]:\n return (termSucThueMorse2(n) for n in count())\n\n# Verificaci\u00f3n\n# ============\n\ndef test_sucThueMorse() -> None:\n r = [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]\n assert list(islice(sucThueMorse(), 30)) == r\n assert list(islice(sucThueMorse2(), 30)) == r\n print(\"Verificado\")\n\n# La verificaci\u00f3n es\n# >>> test_sucThueMorse()\n# Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=100))\ndef test_sucThueMorse_equiv(n: int) -> None:\n assert nth(sucThueMorse(), n) == nth(sucThueMorse2(), n)\n\n# La comprobaci\u00f3n es\n# >>> test_sucThueMorse_equiv()\n# >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n t = Timer(e, \"\", default_timer, globals()).timeit(1)\n print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n# >>> tiempo('nth(sucThueMorse(), 6000)')\n# 2.05 segundos\n# >>> tiempo('nth(sucThueMorse2(), 6000)')\n# 0.01 segundos\n<\/pre>\nReferencias<\/b><\/p>\n\n- N.J.A. Sloane Sucesi\u00f3n A010060<\/a> en OEIS.<\/li>\n
- Programming Praxis: Thue-Morse sequence<\/a>.<\/li>\n
- Wikipedia: Thue\u2013Morse sequence<\/a>.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
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. 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] De esta forma se va formando una sucesi\u00f3n 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,… que se conoce como la sucesi\u00f3n de Thue-Morse. Definir la sucesi\u00f3n sucThueMorse :: [Int]…<\/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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8372"}],"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=8372"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8372\/revisions"}],"predecessor-version":[{"id":8403,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8372\/revisions\/8403"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8372"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8372"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8372"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}