Successió de Thue-Morse

En matemàtiques, la seqüència Thue–Morse o Prouhet–Thue–Morse és la seqüència binària (una seqüència infinita de 0s i 1s) que es pot obtenir començant per 0 i afegint successivament el complement booleà de la seqüència obtinguda fins ara. De vegades s'anomena seqüència de compartició justa per les seves aplicacions a la seqüència de divisió justa o de paritat. Els primers passos d'aquest procediment donen les cadenes 0, 01, 0110, 01101001, 0110100110010110, etc., que són els prefixos de la seqüència Thue–Morse. La seqüència completa comença:

Aquest gràfic mostra la composició repetida i complementària de la seqüència Thue-Morse.

01101001100101101001011001101001....

La seqüència porta el nom d'Axel Thue i Marston Morse.

Definició

Hi ha diverses maneres equivalents de definir la seqüència Thue-Morse.

Quan es compta en binari, la suma de dígits mòdul 2 és la seqüència Thue-Morse

Definició directa

Per calcular l'nè element t_n, escriu el nombre n en binari. Si el nombre d'uns en aquesta expansió binària és senar, aleshores t _n = 1, si és parell llavors t_n = 0. És a dir, t _n és el bit de paritat per a n. John H. Conway et al. nombres considerats n que satisfan t_n = 1 és odiós (pretensió que sigui semblant als senars) i nombres per als quals t_n = 0 per ser nombres dolents (similars a parells).

Generació ràpida de seqüències

Aquest mètode condueix a un mètode ràpid per calcular la seqüència de Thue-Morse: comença amb t₀ = 0, i després, per a cada n, trobeu el bit d'ordre més alt en la representació binària de n que sigui diferent del mateix bit en la representació de n − 1. Si aquest bit està en un índex parell, t_n difereix de t_n − 1, i en cas contrari és el mateix que t_n − 1.

def generate_sequence(seq_length: int):
 """Thue–Morse sequence."""
 value = 1
 for n in range(seq_length):
 # Note: assumes that (-1).bit_length() gives 1
 x = (n ^ (n - 1)).bit_length() + 1
 if x & 1 == 0:
 # Bit index is even, so toggle value
 value = 1 - value
 yield value

L'algorisme resultant triga un temps constant a generar cada element de la seqüència, utilitzant només un nombre logarítmic de bits (nombre constant de paraules) de memòria.

Relació de recurrència

La seqüència Thue–Morse és la seqüència t_n que satisfà la relació de recurrència

${\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}$

per a tots els nombres enters no negatius n.

Sistema L

Seqüència Thue–Morse generada per un sistema L

La seqüència Thue–Morse és una paraula mòrfica: és la sortida del següent sistema de Lindenmayer:

Les variables	0, 1
Constants	Cap
Començar	0
Normes	(0 → 01), (1 → 10)

Propietats

La seqüència Thue–Morse és una paraula uniformement recurrent: donada qualsevol cadena finita X de la seqüència, hi ha una certa longitud n_X (sovint molt més llarga que la longitud d'X) de manera que X apareix en cada bloc de longitud n_X. Notablement, la seqüència de Thue-Morse és uniformement recurrent sense ser ni periòdica ni eventualment periòdica (és a dir, periòdica després d'algun segment inicial no periòdic).