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
|
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 |
import Test.QuickCheck -- 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) -- 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) |
El código se encuentra en GitHub.
Referencias
- N.J.A. Sloane Sucesión A010060 en OEIS.
- Programming Praxis Thue-Morse sequence.
- Wikipedia Thue–Morse sequence