Générateur de Séquence de Moser-de Bruijn | Calculateur de Puissances de 4

Qu’est-ce que la suite de Moser-de Bruijn ?

La suite de Moser-de Bruijn est une liste de nombres entiers qui peuvent chacun s’écrire comme une somme de puissances distinctes de 4. Elle commence par 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, et continue indéfiniment. Elle porte le nom des mathématiciens Leo Moser et Nicolaas Govert de Bruijn. Dans l’Online Encyclopedia of Integer Sequences, elle est répertoriée sous le numéro A000695.

Un nombre appartient à la suite si et seulement si sa représentation en base 4 utilise uniquement les chiffres 0 et 1, jamais 2 ni 3. Par exemple, 21 en base 4 s’écrit 111, donc il appartient à la suite. Le nombre 22 en base 4 s’écrit 112, donc il n’y appartient pas.

Formule de la suite de Moser-de Bruijn

La suite peut être définie de trois manières équivalentes.

Somme de puissances distinctes de 4

Un nombre n appartient à la suite s’il peut s’écrire comme

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

pour un certain ensemble S d’entiers non négatifs, chaque puissance de 4 étant utilisée au plus une fois.

Test des chiffres en base 4

Écrivez le nombre en base 4. Si chaque chiffre est 0 ou 1, le nombre appartient à la suite. Si un chiffre est 2 ou 3, il n’y appartient pas.

Substitution du binaire vers la base 4

En comptant les termes à partir de n = 0, le terme d’indice n est

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

où les $b_i$ sont les chiffres binaires de n. En d’autres termes, écrivez n en binaire, puis lisez chaque chiffre binaire comme un chiffre en base 4 à la même position. C’est la méthode utilisée par le générateur, car elle nécessite seulement de vérifier les bits et d’additionner les nombres.

Comment calculer le n-ième terme

Pour trouver M(n), le générateur effectue les opérations suivantes pour chaque indice n, en commençant par n = 0 :

1. Examiner la forme binaire de n.
2. Pour chaque bit égal à 1, à la position j, ajouter 4^j à un total cumulé.
3. Ignorer les bits égaux à 0.
4. Le total cumulé est M(n).

Exemple détaillé : M(5)

• 5 en binaire vaut 101.
• Le bit 0 (le plus à droite) vaut 1, donc on ajoute 4⁰ = 1.
• Le bit 1 vaut 0, donc on n’ajoute rien.
• Le bit 2 vaut 1, donc on ajoute 4² = 16.
• Total : 1 + 16 = 17.

Ainsi, M(5) = 17. Il s’agit de la sixième valeur produite par le générateur, puisque le comptage commence à M(0).

Exemple : les 32 premiers termes

Comment vérifier qu’un nombre appartient à la suite

Convertissez le nombre en base 4 et lisez ses chiffres.

• 85 : en base 4, 85 s’écrit 1111 (64 + 16 + 4 + 1). Seuls des 0 et des 1 apparaissent, donc 85 appartient à la suite.
• 90 : en base 4, 90 s’écrit 1122. Il contient un 2, donc 90 n’appartient pas à la suite.

Taux de croissance

La suite croît rapidement, car chaque bit supplémentaire de l’indice peut approximativement quadrupler la valeur qu’il ajoute. M(19) vaut 261. M(99) vaut 5 125. M(999), le plus grand terme que ce générateur puisse produire, vaut 349 205. Les termes sont de plus en plus espacés à mesure que l’indice augmente, ce qui rend la suite clairsemée : la plupart des nombres entiers n’y apparaissent jamais, même si elle comporte une infinité de termes.

Comment utiliser le générateur de la suite de Moser-de Bruijn

1. Saisissez le nombre de termes à générer. Le champ prend par défaut la valeur 20 s’il est laissé vide.
2. La liste des termes se met automatiquement à jour, en commençant par M(0).
3. Copiez la liste complète à l’aide du bouton Copy Result.

L’outil accepte les nombres entiers compris entre 1 et 1000. Les nombres décimaux, les nombres négatifs et les entrées non numériques sont refusés. Demander 20 termes renvoie M(0) à M(19) ; la dernière valeur affichée est 261. Tous les calculs sont effectués dans le navigateur, de sorte que les résultats apparaissent immédiatement et qu’aucune donnée n’est envoyée à un serveur.

Suites apparentées

• Puissances de 2 (OEIS A000079) : 1, 2, 4, 8, 16, 32, etc. Elles constituent les éléments de base des nombres binaires ordinaires.
• Sommes de puissances distinctes de 3 (OEIS A005836) : 0, 1, 3, 4, 9, 10, 12, 13, etc. Il s’agit de la même idée que pour la suite de Moser-de Bruijn, construite à partir de la base 3 au lieu de la base 4.
• Nombres fibinaires (OEIS A003714) : 0, 1, 2, 4, 5, 8, 9, 10, etc. Ce sont les nombres dont la forme binaire ne contient pas deux 1 consécutifs.

Historique

Leo Moser (1921-1970) était un mathématicien austro-canadien qui a travaillé en théorie des nombres, en combinatoire et en géométrie. Nicolaas Govert de Bruijn (1918-2012) était un mathématicien néerlandais connu pour ses travaux en combinatoire, en théorie des graphes et en informatique ; ses suites de de Bruijn, sans rapport avec celle-ci, sont largement utilisées en théorie du codage. Tous deux ont étudié les bases additives : des ensembles d’entiers, comme les puissances de 4, à partir desquels chaque nombre représentable possède une représentation comme somme unique. La suite qui porte leurs noms est un exemple d’une telle base.

Foire aux questions

À quoi sert la suite de Moser-de Bruijn ?

Elle intervient en théorie additive des nombres et en combinatoire, notamment dans l’étude des ensembles sans somme et des bases additives. Elle sert aussi à enseigner la conversion de base et les opérations bit à bit en informatique.

Comment générer la suite de Moser-de Bruijn ?

Écrivez l’indice n en binaire, puis lisez chaque chiffre binaire comme un chiffre en base 4 à la même position. Pour n = 5 (binaire 101), on obtient 4² + 4⁰ = 17.

Comment vérifier qu’un nombre appartient à la suite ?

Convertissez-le en base 4. Si chaque chiffre est 0 ou 1, le nombre appartient à la suite. Si un chiffre est 2 ou 3, il n’y appartient pas.

Quelle est la formule du n-ième terme ?

M(n) = la somme, pour tout i, de $b_i \cdot 4^i$, où les $b_i$ sont les chiffres binaires de n.

La suite est-elle infinie ?

Oui. Elle comporte une infinité de termes, même si ceux-ci sont de plus en plus espacés à mesure que n augmente.

En quoi cette suite diffère-t-elle du binaire ?

Le système binaire, c’est-à-dire les sommes de puissances distinctes de 2, permet de représenter tout entier non négatif. La suite de Moser-de Bruijn utilise plutôt les puissances de 4, si bien que la plupart des entiers sont exclus.