Generatore di Sequenza di Moser-de Bruijn | Calcolatore di Potenze di 4

Che cos'è la successione di Moser-de Bruijn?

La successione di Moser-de Bruijn è un elenco di numeri interi, ciascuno dei quali può essere scritto come somma di potenze distinte di 4. Inizia con 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, e continua senza fine. Prende il nome dai matematici Leo Moser e Nicolaas Govert de Bruijn. Nell'Online Encyclopedia of Integer Sequences è catalogata come A000695.

Un numero appartiene alla successione esattamente quando la sua rappresentazione in base 4 usa solo le cifre 0 e 1, mai 2 o 3. Per esempio, 21 in base 4 si scrive 111, quindi appartiene alla successione. Il numero 22 in base 4 si scrive 112, quindi non vi appartiene.

Formula della successione di Moser-de Bruijn

La successione può essere definita in tre modi equivalenti.

Somma di potenze distinte di 4

Un numero n appartiene alla successione se può essere scritto come

$n = \sum_{i \in S} 4^i$

per qualche insieme S di interi non negativi, dove ogni potenza di 4 viene usata al massimo una volta.

Test delle cifre in base 4

Scrivere il numero in base 4. Se ogni cifra è 0 o 1, il numero appartiene alla successione. Se una cifra è 2 o 3, non vi appartiene.

Sostituzione da binario a base 4

Contando i termini a partire da n = 0, il termine all'indice n è

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

dove gli $b_i$ sono le cifre binarie di n. In altre parole: si scrive n in forma binaria, poi si legge ogni cifra binaria come una cifra in base 4 nella stessa posizione. Questo è il metodo usato dal generatore, poiché richiede solo di controllare i bit e sommare i numeri.

Come calcolare l'ennesimo termine

Per trovare M(n), il generatore esegue le seguenti operazioni per ogni indice n, iniziando da n = 0:

1. Osservare la forma binaria di n.
2. Per ogni bit uguale a 1, nella posizione j, aggiungere 4^j a un totale progressivo.
3. Ignorare i bit uguali a 0.
4. Il totale progressivo è M(n).

Esempio svolto: M(5)

• 5 in forma binaria è 101.
• Il bit 0, quello più a destra, è 1, quindi si aggiunge 4⁰ = 1.
• Il bit 1 è 0, quindi non si aggiunge nulla.
• Il bit 2 è 1, quindi si aggiunge 4² = 16.
• Totale: 1 + 16 = 17.

Quindi M(5) = 17. È il sesto valore prodotto dal generatore, poiché il conteggio inizia da M(0).

Esempio: i primi 32 termini

Come verificare se un numero appartiene alla successione

Convertire il numero in base 4 e leggere le sue cifre.

• 85: in base 4, 85 è 1111 (64 + 16 + 4 + 1). Compaiono solo 0 e 1, quindi 85 appartiene alla successione.
• 90: in base 4, 90 è 1122. Contiene un 2, quindi 90 non appartiene alla successione.

Tasso di crescita

La successione cresce rapidamente, perché ogni bit aggiuntivo nell'indice può all'incirca quadruplicare il valore che aggiunge. M(19) è 261. M(99) è 5.125. M(999), il termine più grande che questo generatore può produrre, è 349.205. I termini sono sempre più distanziati man mano che l'indice cresce, rendendo la successione sparsa: la maggior parte dei numeri interi non vi compare mai, anche se contiene infiniti termini.

Come usare il generatore della successione di Moser-de Bruijn

1. Inserire il numero di termini da generare. Se lasciato vuoto, il campo assume per impostazione predefinita il valore 20.
2. L'elenco dei termini si aggiorna automaticamente, a partire da M(0).
3. Copiare l'elenco completo con il pulsante Copy Result.

Lo strumento accetta numeri interi da 1 a 1000. I numeri decimali, negativi e gli inserimenti non numerici vengono rifiutati. La richiesta di 20 termini restituisce da M(0) a M(19); l'ultimo valore visualizzato è 261. Tutti i calcoli vengono eseguiti nel browser, quindi i risultati compaiono immediatamente e nessun dato viene inviato a un server.

Successioni correlate

• Potenze di 2 (OEIS A000079): 1, 2, 4, 8, 16, 32 e così via. Sono gli elementi costitutivi dei normali numeri binari.
• Somme di potenze distinte di 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 e così via. La stessa idea della successione di Moser-de Bruijn, costruita a partire dalla base 3 invece che dalla base 4.
• Numeri fibbinary (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 e così via. Numeri la cui forma binaria non contiene due 1 consecutivi.

Cenni storici

Leo Moser (1921-1970) era un matematico austro-canadese che lavorò nella teoria dei numeri, nella combinatoria e nella geometria. Nicolaas Govert de Bruijn (1918-2012) era un matematico olandese noto per i suoi lavori in combinatoria, teoria dei grafi e informatica; le sue omonime successioni di de Bruijn, non correlate a questa, sono ampiamente usate nella teoria dei codici. Entrambi studiarono le basi additive: insiemi di interi, come le potenze di 4, dai quali ogni numero rappresentabile ha un'unica rappresentazione come somma. La successione che porta i loro nomi è un esempio di tale base.

Domande frequenti

A cosa serve la successione di Moser-de Bruijn?

Ricorre nella teoria additiva dei numeri e nella combinatoria, in particolare nello studio degli insiemi senza somme e delle basi additive. Viene anche usata per insegnare la conversione tra basi e le operazioni bit a bit nell'informatica.

Come si genera la successione di Moser-de Bruijn?

Scrivere l'indice n in forma binaria, poi leggere ogni cifra binaria come una cifra in base 4 nella stessa posizione. Per n = 5 (binario 101), si ottiene 4² + 4⁰ = 17.

Come si verifica se un numero appartiene alla successione?

Convertirlo in base 4. Se ogni cifra è 0 o 1, il numero appartiene alla successione. Se una cifra è 2 o 3, non vi appartiene.

Qual è la formula per l'ennesimo termine?

M(n) = la somma, per tutti gli i, di $b_i \cdot 4^i$, dove gli $b_i$ sono le cifre binarie di n.

La successione è infinita?

Sì. Contiene infiniti termini, anche se diventano più distanziati man mano che n cresce.

In che modo differisce dal sistema binario?

Il sistema binario, cioè le somme di potenze distinte di 2, può rappresentare ogni intero non negativo. La successione di Moser-de Bruijn usa invece le potenze di 4, quindi la maggior parte degli interi viene esclusa.