Système de numération bijectif

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

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

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

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

Démontrons maintenant que tout entier naturel ${\displaystyle n}$ a une décomposition de type ${\displaystyle (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 ${\displaystyle n}$ n'est pas divisible par ${\displaystyle k}$, on choisit le reste de sa division par ${\displaystyle k}$ comme valeur de ${\displaystyle a_{0}}$, et si est divisible par ${\displaystyle k}$, on pose ${\displaystyle a_{0}=k}$. Si ${\displaystyle n=a_{0}}$, on a trouvé une décomposition valable.

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

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

1. ↑ La numération ordinaire en base k ne répond pas à cette définition. Par exemple, en base décimale ordinaire, toutes les suites de longueur supérieure ou égale 2 sont l'image d'un nombre entier : ainsi le nombre 1957 a pour image la suite (1,9,5,7). Comme un système de numération est injectif, la suite (1,9,5,7) n'est l'image que du nombre "1957". Mais, par conséquent, les suites (0,x), ou plus généralement toute suite de longueur supérieure à 1 commençant par "0", ne peut être l'image d'aucun entier.
2. ↑ Raymond Smullyan 1961.
3. ↑ Böhm utilisait ces représentations pour effectuer des calculs dans le langage de programmation P".
4. ↑ Donald Knuth 2007.
5. ↑ Arto Salomaa 1973.
6. ↑ « Représentation des réels » [PDF], sur Alloschool (consulté le 15 mars 2023)
7. ↑ C'est ici la grande différence entre la base k-adique et la base k usuelle : en base k usuelle, on peut avoir un zéro positionnel en ${\displaystyle a_{1}}$. En conséquence, par exemple, "01"="1" : donc deux chaines de longueur différente peuvent représenter le même entier.
8. ↑ Berenice Rojo-Garibaldi, Costanza Rangoni, Diego L. González et Julyan H. E. Cartwright, « Non-power positional number representation systems, bijective numeration, and the Mesoamerican discovery of zero », Heliyon, vol. 7, n^o 3,‎ mars 2021, e06580 (ISSN 2405-8440, PMID 33851058, PMCID 8022160, DOI 10.1016/j.heliyon.2021.e06580, lire en ligne, consulté le 16 mars 2023)
9. ↑ Pour les numérations bijectives de bases k comprises entre 10 et 35, il est d'usage courant d'utiliser les lettres successives de l'alphabet pour désigner les chiffres suivant 9. Par exemple, un système hexadécimal bijectif utilise les seize chiffres {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G}. Un système hexadécimal non bijectif utilise les seize chiffres {0,1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}.
10. ↑ « International Astronomical Union | IAU », sur www.iau.org (consulté le 15 mars 2023)