marc|Aquest gràfic mostra la composició repetida i complementària de la seqüència 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:
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. miniatura|256x256px|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 tn, 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 tn = 0. És a dir, t n és el bit de paritat per a n. John H. Conway et al. nombres considerats n que satisfan tn = 1 és odiós (pretensió que sigui semblant als senars) i nombres per als quals tn = 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 , 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 . Si aquest bit està en un índex parell, tn difereix de , i en cas contrari és el mateix que .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 valueL'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 tn que satisfà la relació de recurrència
per a tots els nombres enters no negatius n.
Sistema L miniatura|256x256px|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 variables0, 1ConstantsCapComençar0Normes(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 nX (sovint molt més llarga que la longitud d'X) de manera que X apareix en cada bloc de longitud nX. 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).
Referències
Categoria:Seqüències d'enters