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
[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] |
[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
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,... |
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
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
λ> 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] |
λ> 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
s(2n) = s(n)
s(2n+1) = 1 - s(n) |
s(2n) = s(n)
s(2n+1) = 1 - s(n)
Soluciones
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) |
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