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 (bien qu'elle puisse prêter à confusion, cette description est celle qu'on trouve dans la littérature. La numération ordinaire en base k, apparemment bijective, ne répond pas à cette définition, à cause de l'absence de zéros de tête ; par exemple, il n'y a que 90 nombres de deux chiffres en base 10, au lieu des 10² qu'elle réclamerait. 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, comme ceci :

• L'entier zéro est représenté par la chaîne vide.

• L'entier représenté par la chaîne de chiffres non vide

a_na_n−1 ... a₁a₀

est

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

• La chaîne représentant l'entier m > 0 est

a_na_n−1 ... a₁a₀

où

a₀ = m − q₀ k,   q₀ = f(m/k);

a₁ = q₀ − q₁ k,  q₁ = f(q₀/k);

a₂ = q₁ − q₂ k,  q₂ = f(q₁/k);

...

a_n = q_n−1 − 0 k, q_n = f(q_n−1/k) = 0;

et

f(x) = pla(x) − 1,

pla(x) étant le plus petit entier non inférieur à x (la fonction plafond).

Propriétés des nombres écrits en base k

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. Voici le classement des premiers nombres 1-, 2-, 3-, and 10-adiques, où ε note la chaîne vide (les représentations binaires et décimales ont été ajoutées à fin de comparaison) :

représentation 1-adique :	ε	1	11	111	1111	11111	...	(système unaire)
représentation 2-adique :	ε	1	2	11	12	21	22	111	112	121	122	211	212	221	222	1111	1112	...
représentation binaire :	0	1	10	11	100	101	110	111	1000	1001	1010	1011	1100	1101	1110	1111	10000	...
représentation 3-adique :	ε	1	2	3	11	12	13	21	22	23	31	32	33	111	112	113	121	...
représentation 10-adique :	ε	1	2	3	4	5	6	7	8	9	A	11	12	13	14	15	16	...
représentation décimale :	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	...

Exemples

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

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

Dans le second exemple, le chiffre "A" représente l'entier dix. Pour 10 ≤ k ≤ 35, on a l'habitude d'utiliser les lettres successives de l'alphabet pour désigner les chiffres suivant 9 ; par exemple, un système hexadécimal bijectif utiliserait les seize chiffres {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G}.

Le système décimal sans zéro

Le système bijectif en base 10 est aussi connu sous le nom de système décimal sans zéro ; comme on l'a dit, il utilise un chiffre supplémentaire, "A", pour représenter 10.

Comme dans le système décimal usuel, chaque position des chiffres représente une puissance de dix, et, par exemple, 123 est "une centaine, plus deux dizaines, plus trois unités". Tous les entiers positifs dont la représentation décimale ne comporte pas de zéros (tels que 123) ont la même représentation dans le système décimal sans zéro. Ceux qui contiennent un zéro doivent être réécrits, ainsi, 10 devient A, 20 devient 1A, 100 devient 9A, 101 devient A1, 302 devient 2A2, 1000 devient 99A, 1110 devient AAA, 2010 devient 19AA, et ainsi de suite.

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 plutôt que la notation conventionnelle 1402.

Le 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 ; il utilise les « chiffres » de "A" à "Z" pour représenter les nombres de 1 à 26. La suite des nombres est A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ... C'est de cette manière que beaucoup de tableurs tels que Microsoft Excel identifient les colonnes de leurs feuilles de calcul.

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^8 + 9 * 26^7 + 11 * 26^6 + 9 * 26^5 + 16 * 26^4 + 5 * 26^3 + 4 * 26^2 + 9 * 26^1 + 1 * 26^0=4878821185187.

Numération systématique utilisant l'alphabet

Le système précédent n'utilise jamais la chaîne vide, et commence donc à compter à partir de 1. Une variante de ce système est utilisée pour nommer les étoiles variables ; il peut plus généralement être utilisé chaque fois qu'on désire une nomenclature systématique utilisant des lettres, et les chaînes de caractères les plus courtes possible.

Notes historiques

Le fait que tout entier naturel possède une représentation unique en numération bijective de base k (k ≥ 1) est un théorème du "folklore mathématique" qui a été redécouvert de nombreuses fois. On le trouve par exemple chez Smullyan (1961) pour le cas k = 2, et chez Böhm (1964) pour tous les k ≥ 1 (Böhm utilisait ces représentations pour effectuer des calculs dans le langage de programmation P′′ (en)). Knuth (1969) mentionne le cas particulier k = 10, et Salomaa (en) (1973) discute les cas k ≥ 2. Forslund (1995) estime que d'anciens systèmes de numération bijectifs auraient pu passer inaperçus dans les documents archéologiques, en raison du manque de familiarité avec eux ; ce dernier article est remarquable par le fait qu'il ne cite pas la littérature existante, mais semble réinventer cette notation de toutes pièces.

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.
• Knuth, D. E. The Art of Computer Programming, Vol. 2 : Seminumerical Algorithms, 1ère ed., Addison-Wesley, 1969. (discute le cas de la base 10 page 495)
• Salomaa, A. (en) Formal Languages, Academic Press, 1973. (Note 9.1, pp. 90-91, discute la base k pour tout k ≥ 2.)
• Smullyan, R. "Theory of Formal Systems", Annals of Mathematics Studies, Number 47, Princeton, 1961.

Liens externes

• Forslund, R. R., : "A logical alternative to the existing positional number system" Southwest Journal of Pure and Applied Mathematics, Volume 1 (September 1995), pp. 27-29. (également disponible en mode texte.)