Stomachion

mercoledì 3 marzo 2021

Numeri odiosi e malvagi

Per capire perché i numeri della sequenza di Thue–Morse o sequenza di Prouhet–Thue–Morse siano odiosi, bisogna prima fornire una loro definizione.
La sequenza venne studiata per la prima volta da Eugène Prouhet nel 1851. Venne successivamente riscoperta nel 1906 da Axel Thue, il primo a menzionarla, e successivamente da Marston Morse nel 1921. La sequenza è una serie infinita di 0 e 1. Si parte da 0 come prima cifra. Il passo successivo è proseguire con il complemento booleano delle cifre precedenti, in questo caso 1. Per cui la sequenza diventa 01.
Al terzo passo si devono aggiungere due cifre, le "negazioni" di 0 e 1, ovvero 10. Per cui la sequenza diventa 0110.
Il complemento booleano di questo terzo passo è 1001, per cui la sequenza diventa 01101001.
Il passo successivo è allora aggiungere alla serie di cifre del quarto passo la seguente serie 10010110, ottenendo la sequenza 0110100110010110, e proseguendo da qui all'infinito!
A questo punto potremmo chiederci come calcolare l'$n$-simo elemento $t_n$ della successione, con $n$ scritto in binario. Ora, se il numero di uni in questa espansione risulta essere dispari, allora $t_n = 1$, altrimenti $t_n = 0$. A questo punto, usando un gioco di parole comprensibile solo in inglese, John Conway ebbe la brillante idea di chiamare i primi numeri odiosi (dispari in inglese è odd, e odioso è odious), e i secondi numeri malvagi (pari in inglese è even, e male è evil).
Per cui se un numero $n$ è odioso, ovvero se la sua espansione binaria presenta un numero dispari di $1$, allora $t_n = 1$, se invece un numero $n$ è malvagio, ovvero se la sua espansione binaria presenta un numero pari di $1$, allora $t_n = 0$.

Nessun commento:

Posta un commento