Système de numération bijectif

En mathématiques, un système de numération bijectif est un système de numération qui établit une bijection entre l'ensemble des entiers naturels et l'ensemble des chaînes finies de « chiffres », pris parmi un ensemble fini. En particulier, la numération bijective en base k représente un entier par une chaîne de chiffres de l'ensemble {1, 2..., k} (k ≥ 1), codant le développement de l'entier en puissances de k . La numération bijective en base k est aussi appelée notation k-adique, à ne pas confondre avec le système des nombres p-adiques. En base 1, on parle de système unaire.

Définition

Le système de numération k-adique utilise l'ensemble des chiffres {1, 2, ..., k} (k ≥ 1) pour représenter chaque entier de manière unique, selon les règles suivantes :

• L'entier zéro est représenté par la chaîne vide.
• La chaîne de chiffres non vide a_na_n−1 ... a₁a₀ représente, en numération k-adique, l'entier qui vaut :

a_n kⁿ + a_n−1 kⁿ⁻¹ + ... + a₁ k¹ + a₀

Tout entier naturel possède une représentation unique en numération bijective de base k (k ≥ 1) comme démontré par Smullyan pour le cas k = 2, Böhm (1964) pour tous les k ≥ 1, Knuth pour k = 10, ou encore Salomaa pour k ≥ 2. Une démonstration simple est donnée ci-dessous.

Démonstration

En nous inspirant de la construction d'un nombre en base $k$ usuelle, démontrons que quel que soit l'entier naturel non nul $k$, tout entier naturel $n$ non nul a une, et une seule, décomposition de la forme : $n=a_{0}+a_{1}\times k+a_{2}\times k^{2}+...+a_{p}\times k^{p}$ où les $a_{j}$ sont des entiers naturels non nuls inférieurs ou égaux à $k$.

Démontrons d'abord que si $n$ a une telle décomposition, elle est unique. Raisonnons par récurrence: si $n$ a deux décompositions notons les $(a_{p},...a_{1},a_{0})$ et $(b_{q},...b_{1},b_{0})$, et démontrons que $b_{0}=a_{0}$.

Si $n$ n'est pas divisible par $k$, le reste de sa division par $k$ est $a_{0}$ mais aussi $b_{0}$. Donc : $b_{0}=a_{0}$. Si $n$ est divisible par $k$, alors $a_{0}=b_{0}=k$ (car aucun $a_{j}$ ou $b_{j}$ ne peut être nul). Donc, dans tous les cas : $a_{0}=b_{0}$. Si $n=a_{0}=b_{0}$, alors $n$ ne peut avoir que la représentation ($a_{0}$), car $n$ est strictement inférieur à tout nombre représenté par un chaine de longueur supérieure se terminant par $a_{0}$.

Si $n>a_{0}$, intéressons nous au nombre entier $(n-a_{0})/k$ : il vaut $a_{1}+a_{2}\times k+...+a_{p}\times k^{p-1}$, mais aussi $b_{1}+b_{2}\times k+...+b_{p}\times k^{p-1}$. Il a donc deux décompositions. Donc, comme démontré ci-dessus, $b_{1}=a_{1}$. Et par récurrence, on démontre que, pour tout $i$, $b_{i}=a_{i}$, donc $n$ n'a qu'une seule décomposition.

Démontrons maintenant que tout entier naturel $n$ a une décomposition de type $(a_{0},a_{1},...,a_{p})$. Pour cela, il suffit d'en construire une, et on peut le faire par récurrence comme suit : si $n$ n'est pas divisible par $k$, on choisit le reste de sa division par $k$ comme valeur de $a_{0}$, et si est divisible par $k$, on pose $a_{0}=k$. Si $n=a_{0}$, on a trouvé une décomposition valable.

Si $n>a_{0}$, alors $n_{1}=n-a_{0}$ est, par construction, un entier non nul qui est divisible par $k$. Appliquons à $n_{1}/k$ la méthode appliquée précédemment pour définir $a_{1}$. Si $n=a_{1}\times k+a_{0}$, on a trouvé une décomposition valable. Sinon, posons : $n_{2}=n-a_{1}\times k-a_{0}$. $n_{2}$ est, par construction, divisible par $k^{2}$. En appliquant la même méthode à $n_{2}/k^{2}$ on définit $a_{2}$ puis, par récurrence, tous les $a_{i}$, et on a ainsi construit une décomposition valable de $n$.

On a donc bien démontré que tout entier naturel non nul $n$ a une décomposition du type recherché, et qu'elle est unique.

Certains historiens des mathématiques estiment que d'anciens systèmes de numération auraient pu être bijectifs, donc sans utilisation du zéro.

Propriétés des nombres écrits en système bijectif

Notation bijective ou usuelle des nombres en base k

Les tableaux ci-dessous donnent quelques exemples de différences de notation de nombres pour différentes bases k entre systèmes usuel et bijectif.

Base	10
Décimal usuel	1	2	9	10	11	20	21	30	99	100	101	110	111	200	1000
10 bijectif	1	2	9	A	11	1A	21	2A	99	9A	A1	AA	111	19A	99A

Base	5
Décimal usuel	1	2	4	5	6	9	10	11	15	20	25	30	31
5 usuel	1	2	4	10	11	14	20	21	30	40	100	110	111
5 bijectif	1	1	4	5	11	14	15	21	25	35	45	55	111

Base	3
Décimal usuel	1	2	3	4	8	9	10	12	13	18	30
3 usuel	1	2	10	11	22	100	101	110	111	200	310
3 bijectif	1	2	3	11	22	23	31	33	111	123	233

Base	2
Décimal usuel	1	2	3	4	5	6	7	8	9	11	15	16
Binaire usuel	1	10	11	100	101	110	111	1000	1001	1011	1111	10000
2 bijectif	1	2	11	12	21	22	111	112	121	211	1111	1112

On remarque :

• qu'un nombre qui s'écrit sans utiliser de zéro en système usuel s'écrit de façon identique en système bijectif, mais qu'il s'écrit différemment dans le cas contraire ;
• que la longueur d'un nombre en notation bijective est inférieure ou égale à celle qu'il a en notation usuelle.

D'autres exemples sont donnés ci-dessous :

(34152)_cinq-adique = 3 × 5⁴ + 4 × 5³ + 1 × 5² + 5 × 5¹ + 2 × 5⁰ = (34152)_cinq = (2427)_décimal.

(119A)_dix-adique = 1 × 10³ + 1 × 10² + 9 × 10¹ + 10 × 10⁰ = (1200)_décimal.

Propriétés

Pour un k donné ≥ 1,

• il y a exactement kⁿ nombres k-adiques de longueur n ≥ 0.
• si k > 1, le nombre de chiffres du nombre k-adique représentant un entier non négatif n est E(log_k(n+1)), contrairement à E(log_k(n)+1) (n > 0) pour la numération ordinaire en base k ; si k = 1 (donc en numération unaire), alors le nombre de chiffres est n ;
• une liste de nombres k-adiques, classée dans l'ordre naturel des entiers représentés, est classée par ordre de longueur, puis, pour chaque longueur donnée, par ordre lexicographique.

Système décimal sans zéro

Le système bijectif en base dix est aussi connu sous le nom de système décimal sans zéro^{[réf. souhaitée]} . Il utilise généralement les chiffres de 1 à 9 et un chiffre supplémentaire, "A", pour représenter dix.

L'addition et la multiplication en système décimal sans zéro utilisent essentiellement les mêmes règles que dans le système usuel, si ce n'est que les retenues se produisent quand un résultat dépasse dix, au lieu de neuf. Ainsi, pour calculer 643 + 759, il y a douze unités (on écrit 2 à droite et on retient 1), dix (9+1) dizaines (on pose A et on ne retient rien), treize centaines (on pose 3 et on retient 1), et un millier, d'où le résultat 13A2, différent de la notation usuelle 1402.

Système bijectif en base 26

Le système bijectif en base 26 est aussi connu sous le nom de base 26 sans zéro^{[réf. souhaitée]}. Plutôt que d'utiliser les chiffres de 1 à 9 complétés des 17 premières lettres de l'alphabet, il est d'usage d'utiliser comme « chiffres » les 26 lettres de l'alphabet (de "A" à "Z") pour représenter les nombres de 1 à 26.

La suite des nombres est donc A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ..., ZY, ZZ, AAA, AAB, AAC, ... C'est de cette manière que beaucoup de tableurs tels que Microsoft Excel identifient les colonnes de leurs feuilles de calcul. Par exemple, dans Excel 2013, il est possible d'utiliser jusqu'à 16384 colonnes, nommées de A à XFD.

Chaque position de chiffre représente une puissance de vingt-six ; ainsi, par exemple, ABC est "une fois 26^2, plus deux fois 26^1, plus trois unités (26^0)" puisque "A" vaut un, "B" vaut deux, et "C" vaut trois.

Dans cette représentation, le nombre WIKIPEDIA est :

23 × 26⁸ + 9 × 26⁷ + 11 × 26⁶ + 9 × 26⁵ + 16 × 26⁴ + 5 × 26³ + 4 × 26² + 9 × 26¹ + 1 × 26⁰ = 4878821185187

Une variante de ce système est partiellement utilisée pour nommer les étoiles variables.

Plus généralement, le système bijectif à base 26 peut être utilisé chaque fois qu'on désire une nomenclature systématique n'utilisant que des lettres avec les chaînes de caractères les plus courtes possible.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bijective numeration » (voir la liste des auteurs).

Sources

• Böhm, C. "On a family of Turing machines and the related programming language", ICC Bulletin 3, p. 191, July 1964.

Bibliographie

• (en) Raymond Smullyan, Theory of formal systems, Princeton, New Jersey, Princeton University Press, 1961 (réimpr. 1968), 149 p. (lire en ligne)
• (en) Arto Salomaa, Formal Languages, New York, Academic Press, 1973, 344 p. (lire en ligne)
• (en) Donald Knuth, The Art of Computer Programming Vol 2 Seminumerical Algorithms, USA, Addison-Wesley, 2007 (1^re éd. 1998), 792 p. (ISBN 0-201-89684-2, lire en ligne),