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 [1]. 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 anan−1 ... a1a0 représente, en numération k-adique, l'entier qui vaut :
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[2], Böhm (1964) pour tous les k ≥ 1[3], Knuth pour k = 10[4], ou encore Salomaa pour k ≥ 2[5]. Une démonstration simple est donnée ci-dessous.
En nous inspirant de la construction d'un nombre en base usuelle[6], démontrons que quel que soit l'entier naturel non nul , tout entier naturel non nul a une, et une seule, décomposition de la forme : où les sont des entiers naturels non nuls inférieurs ou égaux à .
Démontrons d'abord que si a une telle décomposition, elle est unique. Raisonnons par récurrence: si a deux décompositions notons les et , et démontrons que .
Si n'est pas divisible par , le reste de sa division par est mais aussi . Donc : . Si est divisible par , alors (car aucun ou ne peut être nul). Donc, dans tous les cas : . Si , alors ne peut avoir que la représentation (), car est strictement inférieur à tout nombre représenté par un chaine de longueur supérieure se terminant par [7].
Si , intéressons nous au nombre entier : il vaut , mais aussi . Il a donc deux décompositions. Donc, comme démontré ci-dessus, . Et par récurrence, on démontre que, pour tout , , donc n'a qu'une seule décomposition.
Démontrons maintenant que tout entier naturel a une décomposition de type . Pour cela, il suffit d'en construire une, et on peut le faire par récurrence comme suit : si n'est pas divisible par , on choisit le reste de sa division par comme valeur de , et si est divisible par , on pose . Si , on a trouvé une décomposition valable.
Si , alors est, par construction, un entier non nul qui est divisible par . Appliquons à la méthode appliquée précédemment pour définir . Si , on a trouvé une décomposition valable. Sinon, posons : . est, par construction, divisible par . En appliquant la même méthode à on définit puis, par récurrence, tous les , et on a ainsi construit une décomposition valable de .
On a donc bien démontré que tout entier naturel non nul 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[8].
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[9].
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 × 54 + 4 × 53 + 1 × 52 + 5 × 51 + 2 × 50 = (34152)cinq = (2427)décimal.
- (119A)dix-adique = 1 × 103 + 1 × 102 + 9 × 101 + 10 × 100 = (1200)décimal.
Propriétés
Pour un k donné ≥ 1,
- il y a exactement kn 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(logk(n+1)), contrairement à E(logk(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 × 268 + 9 × 267 + 11 × 266 + 9 × 265 + 16 × 264 + 5 × 263 + 4 × 262 + 9 × 261 + 1 × 260 = 4878821185187
Une variante de ce système est partiellement utilisée pour nommer les étoiles variables[10].
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).
- ↑ 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.
- ↑ Raymond Smullyan 1961.
- ↑ Böhm utilisait ces représentations pour effectuer des calculs dans le langage de programmation P".
- ↑ Donald Knuth 2007.
- ↑ Arto Salomaa 1973.
- ↑ « Représentation des réels » [PDF], sur Alloschool (consulté le )
- ↑ 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 . En conséquence, par exemple, "01"="1" : donc deux chaines de longueur différente peuvent représenter le même entier.
- ↑ 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, no 3, , e06580 (ISSN 2405-8440, PMID 33851058, PMCID 8022160, DOI 10.1016/j.heliyon.2021.e06580, lire en ligne, consulté le )
- ↑ 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}.
- ↑ « International Astronomical Union | IAU », sur www.iau.org (consulté le )
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, (réimpr. 1968), 149 p. (lire en ligne)
- (en) Arto Salomaa, Formal Languages, New York, Academic Press, , 344 p. (lire en ligne)
- (en) Donald Knuth, The Art of Computer Programming Vol 2 Seminumerical Algorithms, USA, Addison-Wesley, (1re éd. 1998), 792 p. (ISBN 0-201-89684-2, lire en ligne),
v · m | |
---|---|
Arabo-indiennes | |
Positionnelles |
|
Asiatiques orientales | |
Alphabétiques |
|
Additives |
|
Voir aussi : |
v · m Base de numération positionnelle | ||
---|---|---|
1 à 9 | unaire (1), binaire (2), ternaire (3), quaternaire (4), quinaire (5), sénaire (6), septénaire (7), octal (8), nonaire (9) | ![]() |
10 à 60 | décimal (10), undécimal (11), duodécimal (12), tridécimal (13), quindécimal (15), hexadécimal (16), octodécimal (18), vicésimal (20), base 36, sexagésimal (60) | |
Autre base | base d'or (φ), mixte, négabinaire (–2), négaternaire (-3), bases complexes (en) : quater-imaginaire (2i) | |
Notions |
Portail des mathématiques