La sucesión de Thue-Morse
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son
1 2 3 4 5 |
[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ón
1 |
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,... |
que se conoce como la sucesión de Thue-Morse.
Definir la sucesión
1 |
sucThueMorse :: [Int] |
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
1 2 3 4 5 6 |
λ> take 30 sucThueMorse [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] λ> map (sucThueMorse4 !!) [1234567..1234596] [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] λ> map (sucThueMorse4 !!) [4000000..4000030] [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] |
Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces
1 2 |
s(2n) = s(n) s(2n+1) = 1 - s(n) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
module La_sucesion_de_Thue_Morse where import Test.QuickCheck import Test.Hspec (Spec, describe, hspec, it, shouldBe) -- 1ª solución -- =========== sucThueMorse1 :: [Int] sucThueMorse1 = map termSucThueMorse1 [0..] -- (termSucThueMorse1 n) es el n-ésimo término de la sucesión de -- Thue-Morse. Por ejemplo, -- termSucThueMorse1 0 == 0 -- termSucThueMorse1 1 == 1 -- termSucThueMorse1 2 == 1 -- termSucThueMorse1 3 == 0 -- termSucThueMorse1 4 == 1 termSucThueMorse1 :: Int -> Int termSucThueMorse1 0 = 0 termSucThueMorse1 n = (serieThueMorse !! k) !! n where k = 1 + floor (logBase 2 (fromIntegral n)) -- serieThueMorse es la lista cuyos elementos son los términos de la -- serie de Thue-Morse. Por ejemplo, -- λ> take 4 serieThueMorse3 -- [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]] serieThueMorse :: [[Int]] serieThueMorse = iterate paso [0] where paso xs = xs ++ map (1-) xs -- 2ª solución -- =========== sucThueMorse2 :: [Int] sucThueMorse2 = 0 : intercala (map (1-) sucThueMorse2) (tail sucThueMorse2) -- (intercala xs ys) es la lista obtenida intercalando los elementos de -- las listas infinitas xs e ys. Por ejemplo, -- take 10 (intercala [1,5..] [2,4..]) == [1,2,5,4,9,6,13,8,17,10] intercala :: [a] -> [a] -> [a] intercala (x:xs) ys = x : intercala ys xs -- 3ª solución -- =========== sucThueMorse3 :: [Int] sucThueMorse3 = 0 : 1 : aux (tail sucThueMorse3) where aux (x : xs) = x : (1 - x) : aux xs -- 4ª solución -- =========== sucThueMorse4 :: [Int] sucThueMorse4 = 0 : aux [1] where aux xs = xs ++ aux (xs ++ map (1-) xs) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_termSucThueMorse :: NonNegative Int -> Bool prop_termSucThueMorse (NonNegative n) = sucThueMorse1 !! (2*n) == sn && sucThueMorse1 !! (2*n+1) == 1 - sn where sn = sucThueMorse1 !! n -- La comprobación es -- λ> quickCheck prop_termSucThueMorse -- +++ OK, passed 100 tests. -- 5ª solución -- =========== sucThueMorse5 :: [Int] sucThueMorse5 = map termSucThueMorse5 [0..] -- (termSucThueMorse5 n) es el n-ésimo término de la sucesión de -- Thue-Morse. Por ejemplo, -- termSucThueMorse5 0 == 0 -- termSucThueMorse5 1 == 1 -- termSucThueMorse5 2 == 1 -- termSucThueMorse5 3 == 0 -- termSucThueMorse5 4 == 1 termSucThueMorse5 :: Int -> Int termSucThueMorse5 0 = 0 termSucThueMorse5 n | even n = termSucThueMorse5 (n `div` 2) | otherwise = 1 - termSucThueMorse5 (n `div` 2) -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: [Int] -> Spec specG sucThueMorse = do it "e1" $ take 30 sucThueMorse `shouldBe` [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] spec :: Spec spec = do describe "def. 1" $ specG sucThueMorse1 describe "def. 2" $ specG sucThueMorse2 describe "def. 3" $ specG sucThueMorse3 describe "def. 4" $ specG sucThueMorse4 describe "def. 5" $ specG sucThueMorse5 -- La verificación es -- λ> verifica -- -- 5 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sucThueMorse :: NonNegative Int -> Bool prop_sucThueMorse (NonNegative n) = all (== sucThueMorse1 !! n) [sucThueMorse2 !! n, sucThueMorse3 !! n, sucThueMorse4 !! n, sucThueMorse5 !! n] -- La comprobación es -- λ> quickCheck prop_sucThueMorse -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sucThueMorse1 !! (10^7) -- 0 -- (3.28 secs, 3,420,080,168 bytes) -- λ> sucThueMorse2 !! (10^7) -- 0 -- (3.01 secs, 1,720,549,640 bytes) -- λ> sucThueMorse3 !! (10^7) -- 0 -- (1.80 secs, 1,360,550,040 bytes) -- λ> sucThueMorse4 !! (10^7) -- 0 -- (0.88 secs, 1,254,772,768 bytes) -- λ> sucThueMorse5 !! (10^7) -- 0 -- (0.62 secs, 1,600,557,072 bytes) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
from itertools import count, islice from math import floor, log2 from timeit import Timer, default_timer from typing import Iterator, TypeVar from hypothesis import given from hypothesis import strategies as st from src.La_serie_de_Thue_Morse import serieThueMorse A = TypeVar('A') # 1ª solución # =========== # nth(i, n) es el n-ésimo elemento del iterador i. def nth(i: Iterator[A], n: int) -> A: return list(islice(i, n, n+1))[0] # termSucThueMorse(n) es el n-ésimo término de la sucesión de # Thue-Morse. Por ejemplo, # termSucThueMorse(0) == 0 # termSucThueMorse(1) == 1 # termSucThueMorse(2) == 1 # termSucThueMorse(3) == 0 # termSucThueMorse(4) == 1 def termSucThueMorse(n: int) -> int: if n == 0: return 0 k = 1 + floor(log2(n)) return nth(serieThueMorse(), k)[n] def sucThueMorse() -> Iterator[int]: return (termSucThueMorse(n) for n in count()) # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=100)) def test_prop_termSucThueMorse(n: int) -> None: sn = nth(sucThueMorse(), n) assert nth(sucThueMorse(), 2*n) == sn assert nth(sucThueMorse(), 2*n+1) == 1 - sn # La comprobación es # >>> test_prop_termSucThueMorse() # >>> # 2ª solución # =========== # termSucThueMorse2(n) es el n-ésimo término de la sucesión de # Thue-Morse. Por ejemplo, # termSucThueMorse2(0) == 0 # termSucThueMorse2(1) == 1 # termSucThueMorse2(2) == 1 # termSucThueMorse2(3) == 0 # termSucThueMorse2(4) == 1 def termSucThueMorse2(n: int) -> int: if n == 0: return 0 if n % 2 == 0: return termSucThueMorse2(n // 2) return 1 - termSucThueMorse2(n // 2) def sucThueMorse2() -> Iterator[int]: return (termSucThueMorse2(n) for n in count()) # Verificación # ============ def test_sucThueMorse() -> None: 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] assert list(islice(sucThueMorse(), 30)) == r assert list(islice(sucThueMorse2(), 30)) == r print("Verificado") # La verificación es # >>> test_sucThueMorse() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=100)) def test_sucThueMorse_equiv(n: int) -> None: assert nth(sucThueMorse(), n) == nth(sucThueMorse2(), n) # La comprobación es # >>> test_sucThueMorse_equiv() # >>> # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('nth(sucThueMorse(), 6000)') # 2.05 segundos # >>> tiempo('nth(sucThueMorse2(), 6000)') # 0.01 segundos |
Referencias
- N.J.A. Sloane Sucesión A010060 en OEIS.
- Programming Praxis: Thue-Morse sequence.
- Wikipedia: Thue–Morse sequence.