Système de numération bijectif

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).

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-, et 10-adiques, où ε note la chaîne vide (les représentations binaires et décimales ont été ajoutées à fin de comparaison) :

(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 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 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, ..., 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

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 (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.

• (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).

• 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.)

• Portail des mathématiques