Ir al contenido principal

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

[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,...

que se conoce como la sucesión de Thue-Morse.

Definir la sucesión

sucThueMorse :: [Int]

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]

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)

Soluciones

import Test.QuickCheck

-- 1ª definición (basada en la serie de Thue-Morse)
-- ================================================

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

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_termSucThueMorse :: Int -> Property
prop_termSucThueMorse n =
    n > 0 ==>
      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.

-- 2ª definición (basada en la propiedad anterior)
-- ===============================================

sucThueMorse2 :: [Int]
sucThueMorse2 = map termSucThueMorse2 [0..]

-- (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
termSucThueMorse2 :: Int -> Int
termSucThueMorse2 0 = 0
termSucThueMorse2 n
    | even n    = termSucThueMorse2 (n `div` 2)
    | otherwise = 1 - termSucThueMorse2 (n `div` 2)

-- 3ª definición
-- =============

sucThueMorse3 :: [Int]
sucThueMorse3 =
   0 : intercala (map (1-) sucThueMorse3) (tail sucThueMorse3)

-- (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

-- 4ª definición
-- =============

sucThueMorse4 :: [Int]
sucThueMorse4 = 0 : aux [1]
    where aux xs = xs ++ aux (xs ++ map (1-) xs)

-- 5ª definición
-- =============

sucThueMorse5 :: [Int]
sucThueMorse5 = 0 : 1 : aux (tail sucThueMorse5)
    where aux = (\(x:xs) -> x : (1 - x) : aux xs)

-- Comparación de eficiencia
-- =========================

--    λ> sucThueMorse1 !! 2000000
--    1
--    (1.78 secs, 620,335,144 bytes)
--    λ> sucThueMorse2 !! 2000000
--    1
--    (0.34 secs, 197,790,760 bytes)
--    λ> sucThueMorse3 !! 2000000
--    1
--    (1.70 secs, 332,015,856 bytes)
--    λ> sucThueMorse4 !! 2000000
--    1
--    (0.17 secs, 0 bytes)
--    λ> sucThueMorse5 !! 2000000
--    1
--    (1.74 secs, 319,026,688 bytes)
import Test.QuickCheck

-- 1ª definición (basada en la serie de Thue-Morse)
-- ================================================

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

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_termSucThueMorse :: Int -> Property
prop_termSucThueMorse n =
    n > 0 ==>
      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.

-- 2ª definición (basada en la propiedad anterior)
-- ===============================================

sucThueMorse2 :: [Int]
sucThueMorse2 = map termSucThueMorse2 [0..]

-- (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
termSucThueMorse2 :: Int -> Int
termSucThueMorse2 0 = 0
termSucThueMorse2 n
    | even n    = termSucThueMorse2 (n `div` 2)
    | otherwise = 1 - termSucThueMorse2 (n `div` 2)

-- 3ª definición
-- =============

sucThueMorse3 :: [Int]
sucThueMorse3 =
   0 : intercala (map (1-) sucThueMorse3) (tail sucThueMorse3)

-- (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

-- 4ª definición
-- =============

sucThueMorse4 :: [Int]
sucThueMorse4 = 0 : aux [1]
    where aux xs = xs ++ aux (xs ++ map (1-) xs)

-- Comparación de eficiencia

--    λ> sucThueMorse1 !! 2000000
--    1
--    (2.28 secs, 1,000,302,296 bytes)
--    λ> sucThueMorse2 !! 2000000
--    1
--    (0.46 secs, 237,665,760 bytes)
--    λ> sucThueMorse3 !! 2000000
--    1
--    (1.84 secs, 435,645,232 bytes)
--    λ> sucThueMorse4 !! 2000000
--    1
--    (0.23 secs, 0 bytes)

Referencias