Sucesión de Thue-Morse

Demostración gráfica de la sucesión de Thue-Morse basada en el complemento de la secuencia existente.

En matemáticas, la sucesión de Thue-Morse (también conocida como sucesión de Prouhet-Thue-Morse) es una sucesión de dígitos binarios que si se concatenan produce una secuencia con segmentos iniciales alternos. La secuencia se obtiene comenzando con un cero y añadiendo sucesivamente el complemento Booleano de la secuencia que existe al momento. De esta forma, la secuencia comienza con 0, 01, 0110, 01101001, 0110100110010110...(sucesión A010060 en OEIS)

Definición

Existen varias definiciones equivalentes de la sucesión de Thue-Morse:

Definición directa

Para calcular el nésimo elemento tn, se escribe el número n en binario. Si el total de números 1 en esta expansión binaria es impar, entonces tn = 1; si es par, entonces tn = 0.[1] Es por esta razón que John H. Conway et al. le llamó a los números n que satisfacen tn = 1 números odiosos (basándose en la palabra inglesa odd, "impar") y a los númerps que satisfacentn = 0 como números malignos (basándose en la palabra inglesa even, "par").

Relación de recurrencia

Esta secuencia se obtiene mediante una sucesión de dígitos binarios que satisface la siguiente relación de recurrencia:

Para todo valor entero positivo de n.

Es decir, si representamos los dígitos binarios como 0 y 1 la secuencia de Thue-Morse tiene la siguiente forma:

01101001100101101001011001101001...

Esta secuencia, tomada como la parte decimal de un número en base 2 es conocida como constante de Thue-Morse:

0,01101001100101101001011001101001...2 = 0.41245403364...10

que es un número trascendental como o como .

Caracterización a través de negación a nivel de bits

Una definición alternativa es a través de un algoritmo que utiliza el negador binario a nivel de bit (~) y la concatenación de cadenas de dígitos (+).

  1. X:= 0.
  2. REPETIR MIENTRAS LONGITUD(X) < LONGITUD_TERMINAL
  3.    Y:= ~X
  4.    X:= X+Y
  5. DEVOLVER X


De esta forma, el primer elemento es 0. Luego, una vez que se han especificado los primeros 2n elementos, formando una cadena s, entonces los siguientes 2n elementos deben formar la negación a nivel de bit de s. Ahora se han definido los primeros 2n+1 elementos y se repite la operación.

En particular, estos primeros pasos son los siguientes:

  • Se empieza con un 0.
  • La negación a nivel de bit de 0 es 1.
  • Al combinar (o concatenar) éstos, los primeros elementos son 01.
  • La negación a nivel de bit de 01 es 10.
  • Al combinar éstos, los primeros 4 elementos son 0110.
  • La negación a nivel de bit de 0110 es 1001.
  • Al combinar éstos, los primeros 8 elementos son 01101001.
  • Y así sucesivamente.

De esta forma,

  • T0 = 0.
  • T1 = 01.
  • T2 = 0110.
  • T3 = 01101001.
  • T4 = 0110100110010110.
  • T5 = 01101001100101101001011001101001.
  • T6 = 0110100110010110100101100110100110010110011010010110100110010110.
  • Y así sucesivamente.

Producto infinito

La sucesión también se puede definir mediante el siguiente producto:

donde tj es el j-simo elemento si comenzamos en j = 0.

Other Languages