Exercitium

La sucesión de Thue-Morse
Publicado el 14 de enero de 2024 por José A. Alonso

Índice

1. Enunciado

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)

2. Soluciones en Haskell

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)

3. Soluciones en Python

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

4. Referencias

Exercitium

José A. Alonso Jiménez

Sevilla, 07 de abril del 2024

Licencia: Creative Commons.