Numération à bases mixtes

Un système de numération à bases mixtes, dit aussi à bases de Cantor^[1], ou encore en base à pas variable^[2], est un système de numération dans lequel la base varie selon sa place dans la notation positionnelle du nombre, au lieu d'être fixe, comme c'est le cas, par exemple dans le système décimal où la base est toujours 10, ou dans le système binaire où la base est toujours 2.

On trouve de tels systèmes en métrologie. L'exemple le plus courant est le comptage du temps où une semaine compte 7 jours ; un jour, 24 heures ; une heure, 60 minutes une minute, 60 secondes ; une seconde, 100 centièmes de seconde.

En mathématiques, l'utilisation d'une numération à bases mixtes permet parfois de simplifier certains problèmes.

Soit ${\displaystyle (b_{i})_{i\geqslant 1}}$ une suite d'entiers strictement supérieurs à 1. On construit la suite ${\displaystyle (\pi _{i})_{i\geqslant 0}}$ en posant ${\displaystyle \pi _{0}=1}$ et pour tout ${\displaystyle i}$, ${\displaystyle \pi _{i+1}=\pi _{i}\times b_{i+1}}$.

Alors pour tout entier naturel ${\displaystyle N}$ non nul, il existe un entier naturel ${\displaystyle k}$ et ${\displaystyle k+1}$ entiers ${\displaystyle a_{0},a_{1},\cdots ,a_{k}}$ tels que

• ${\displaystyle a_{k}\neq 0}$
• pour tout ${\displaystyle i}$, ${\displaystyle a_{i}<b_{i+1}}$
• ${\displaystyle N=\sum _{i=0}^{k}a_{i}\pi _{i}=a_{0}+a_{1}b_{1}+a_{2}b_{1}b_{2}+...+a_{k}b_{1}b_{2}..b_{k}=a_{0}+b_{1}\left(a_{1}+b_{2}\left(a_{2}+b_{3}\left(a_{3}+\cdots +a_{k}b_{k}\right)\right)\right)}$.

De plus cette décomposition est unique et représente l'expression du nombre ${\displaystyle N}$ dans le système de bases ${\displaystyle (b_{i})_{i\geq 1}}$.

Dans le cas où tous les ${\displaystyle b_{i}}$ sont égaux à ${\displaystyle b}$, on retrouve le système de numération de base ${\displaystyle b}$.

Dans le tableau ci-dessous, on indique, pour chaque rang, le poids du rang, la valeur maximale que peut prendre ${\displaystyle a_{i}}$, le plus grand nombre que l'on peut écrire avec ${\displaystyle i+1}$ chiffres

Caractéristiques du système

Rang i	0	1	2	3	...	k	...
Poids du rang	1	${\displaystyle b_{1}}$	${\displaystyle b_{1}b_{2}}$	${\displaystyle b_{1}b_{2}b_{3}}$	...	${\displaystyle \pi _{k}}$	...
Valeur max de ${\displaystyle a_{i}}$	${\displaystyle b_{1}-1}$	${\displaystyle b_{2}-1}$	${\displaystyle b_{3}-1}$	${\displaystyle b_{4}-1}$	...	${\displaystyle b_{k+1}-1}$	...
Valeur max de N	${\displaystyle b_{1}-1}$	${\displaystyle b_{1}b_{2}-1}$	${\displaystyle b_{1}b_{2}b_{3}-1}$	${\displaystyle b_{1}b_{2}b_{3}b_{4}-1}$	...	${\displaystyle \pi _{k+1}-1}$	...

Si l'on cherche à écrire le nombre selon un système positionnel comme dans le système de base 10, on se heurte à deux problèmes. D'une part, les ${\displaystyle b_{i}}$ pouvant dépasser 10, l'écriture des ${\displaystyle a_{i}}$ risque de nécessiter d'autres chiffres que 0, 1, 2, ..., 9. D'autre part, les ${\displaystyle b_{i}}$ étant variables, il parait judicieux de préciser quelque part leurs valeurs. Le premier problème peut se résoudre, comme pour l'écriture en système sexagésimal, en écrivant les ${\displaystyle a_{i}}$ en décimal et en insérant un séparateur entre chaque «chiffre». Ainsi, si

${\displaystyle N={\color {Red}50}+{\color {Red}15}\times 60+{\color {Red}13}\times 60\times 60+{\color {Red}5}\times 60\times 60\times 24+{\color {Red}4}\times 60\times 60\times 24\times 7(=2\,898\,950).}$

on peut écrire

${\displaystyle N=4;5;13;15;50.}$

Le second problème peut se résoudre en indiquant des unités (en métrologie)

${\displaystyle N}$ = 4 semaines, 5 jours, 13 heures, 15 minutes, 50 secondes.

ou bien en indiquant en indice la valeur qui fait changer de rang^[3], c'est-à-dire ${\displaystyle b_{i+1}}$:

${\displaystyle N=4_{\infty }5_{7}13_{24}15_{60}50_{60}.}$

En 1869, Georg Cantor a prouvé^[4] que les systèmes de numération permettant de représenter les entiers naturels de manière univoque étaient nécessairement de la forme décrite ci-dessus. Plus précisément: si ${\displaystyle (\pi _{i})}$ est une suite strictement croissante d'entiers naturels, pour que, pour tout entier ${\displaystyle N}$ non nul, il existe toujours un entier ${\displaystyle k}$ et ${\displaystyle k+1}$ entiers ${\displaystyle a_{0},a_{1},\cdots ,a_{k}}$ uniques tels que

${\displaystyle N=\sum _{i=0}^{k}a_{i}\pi _{i}}$

il est nécessaire et suffisant que

• ${\displaystyle \pi _{0}=1}$
• pour tout ${\displaystyle i}$, ${\displaystyle \pi _{i+1}}$ soit un multiple de ${\displaystyle \pi _{i}}$, i.e. ${\displaystyle \pi _{i+1}=\pi _{i}\times b_{i+1}}$ avec ${\displaystyle b_{i+1}>1}$.
• pour tout ${\displaystyle i}$, ${\displaystyle a_{i}<b_{i+1}}$ et ${\displaystyle a_{k}\neq 0}$

Soit ${\displaystyle (b_{i})_{i\geqslant 1}}$ une suite d'entiers strictement supérieurs à 1. On construit la suite ${\displaystyle (\pi _{i})_{i\geqslant 0}}$ en posant ${\displaystyle \pi _{0}=1}$ et pour tout ${\displaystyle i}$, ${\displaystyle \pi _{i+1}=\pi _{i}\times b_{i+1}}$.

Alors pour tout réel ${\displaystyle x}$ tel que ${\displaystyle 0\leqslant x<1}$, il existe une suite d'entiers ${\displaystyle (a_{i})_{i\geqslant 1}}$ telle que

• pour tout ${\displaystyle i}$, ${\displaystyle a_{i}<b_{i}}$
• ${\displaystyle x=\sum _{i=1}^{+\infty }{\frac {a_{i}}{\pi _{i}}}={\frac {a_{1}}{b_{1}}}+{\frac {a_{2}}{b_{1}b_{2}}}+\cdots }$

De plus cette décomposition est unique dès que ${\displaystyle x\pi _{i}}$ n'est jamais entier^[5]. S'il existe ${\displaystyle k}$ tel que ${\displaystyle x\pi _{k}}$ est entier, ${\displaystyle x}$ possède deux décompositions^[5], une telle que, pour tout ${\displaystyle i>k}$, ${\displaystyle a_{i}=0}$, l'autre pour laquelle pour tout ${\displaystyle i>k}$, ${\displaystyle a'_{i}=b_{i}-1}$.

La construction d'une décomposition utilise une méthode analogue à la division longue : on définit les suites ${\displaystyle a_{i}}$ et ${\displaystyle x_{i}}$ en posant^[6]

• ${\displaystyle x_{1}=x}$
• pour tout ${\displaystyle i}$, ${\displaystyle a_{i}}$ et ${\displaystyle x_{i+1}}$ sont respectivement la partie entière et la partie fractionnaire de ${\displaystyle b_{i}x_{i}}$.

Remarque : si tous les ${\displaystyle a_{i}}$ sont égaux à 1, le réel ${\displaystyle x=\sum _{i=1}^{+\infty }{\frac {1}{b_{1}b_{2}\cdots b_{i}}}}$ a pour développement de Engel ${\displaystyle ]b_{1},b_{2},b_{3},...[}$.

Soit ${\displaystyle (b_{i})_{i\geqslant 1}}$ une suite d'entiers strictement supérieurs à 1 et la suite ${\displaystyle \pi _{i}=\prod _{j=1}^{i}b_{j}}$. On suppose que, pour tout entier ${\displaystyle q}$, ${\displaystyle q}$ divise les ${\displaystyle \pi _{i}}$ à partir d'un certain rang. Soit ${\displaystyle x}$ un réel, si le développement de sa partie fractionnaire selon la base ${\displaystyle (b_{i})_{i\geqslant 1}}$ ne se termine ni par une suite de 0 ni par une suite de ${\displaystyle a_{i}=b_{i}-1}$ alors ce nombre est irrationnel^[7]. Dit autrement, si tout nombre premier ${\displaystyle p}$ divise une infinité de ${\displaystyle b_{i}}$ et si le développement de la partie fractionnaire de ${\displaystyle x}$ selon la base ${\displaystyle (b_{i})_{i\geqslant 1}}$ contient une infinité de termes ${\displaystyle a_{i}}$ différents de 0 et une infinité de termes différents de ${\displaystyle b_{i}-1}$, alors ${\displaystyle x}$ est un irrationnel^[8].

Si la suite ${\displaystyle (b_{i})_{i\geqslant 1}}$ est périodique à partir d'un certain rang, alors un réel ${\displaystyle x}$ est rationnel si et seulement si le développement de sa partie fractionnaire dans la base ${\displaystyle (b_{i})_{i\geq 1}}$ est périodique à partir d'un certain rang^[9].

Le comptage du temps est l'exemple le plus simple et le plus courant de système à bases multiples. Ce système de comptage était extrêmement courant, au delà du comptage du temps, avant que ne se généralisent les mesures en système décimal. Le système monétaire anglais avant 1971, utilisait un système de base mixte puisque la livre valait 20 shillings et le shilling 12 pence. Les systèmes de numération sumériens des IV^e et III^e millénaires utilisaient un système additif avec unités dont la base variait. Ainsi pour énumérer des produits consommables, ils utilisaient le système mixte suivant :

Caractéristiques du système sumérien pour consommables^[10]

Rang i	0	1	2	3	4	5
Poids du rang	1	10	60	120	1200	7200
Valeur max de ${\displaystyle a_{i}}$	9	5	1	9	5	...

Le système de comptage du temps maya utilise un systeme de numération positionnel dont tous les ${\displaystyle b_{i}}$ valent 20 à l'exception de ${\displaystyle b_{2}}$ qui vaut 18^[11].

Dans ce système, la suite des ${\displaystyle (b_{i})_{i\geq 1}}$ est la suite des entiers consécutifs à partir de 2, et la suite ${\displaystyle \pi _{i}}$ est définie par ${\displaystyle \pi _{i}=(i+1)!}$ où ${\displaystyle (i+1)!}$ est la factorielle du nombre ${\displaystyle i+1}$, c'est-à-dire le produit de tous les entiers de 1 jusqu'à ${\displaystyle (i+1)}$. Ce système a les caractéristiques suivantes :

Caractéristiques du système factoriel

Rang i	0	1	2	3	...	k	...
Poids du rang	1	2	${\displaystyle 2\times 3=6}$	${\displaystyle 2\times 3\times 4=24}$	...	${\displaystyle (i+1)!}$	...
Valeur max de ${\displaystyle a_{i}}$	${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 4}$	...	${\displaystyle i+1}$	...
Valeur max de N	${\displaystyle 1}$	${\displaystyle 5}$	${\displaystyle 23}$	${\displaystyle 119}$	...	${\displaystyle (i+2)!-1}$	...

Dans ce système un entier naturel s'écrit

${\displaystyle N=\sum _{i=0}^{k}(i+1)!a_{i}=a_{0}+2a_{1}+6a_{2}+...+(k+1)!a_{k}}$

et un réel ${\displaystyle x}$ s'écrit

${\displaystyle x=\left\lfloor x\right\rfloor +\sum _{i=1}^{+\infty }{\frac {a_{i}}{(i+1)!}}=\left\lfloor x\right\rfloor +{\frac {a_{1}}{2}}+{\frac {a_{2}}{6}}+\cdots }$

Par exemple, ${\displaystyle e=2+\sum _{i=1}^{+\infty }{\frac {1}{(i+1)!}}}$ a tous ses coefficients ${\displaystyle a_{i}}$ égaux à 1.

Grâce au code de Lehmer, il est possible d'affecter à toute permutation d'un ensemble à ${\displaystyle n}$ éléments un numéro avec au plus ${\displaystyle n}$ chiffres en base factorielle^[12].

Dans ce système, la suite des ${\displaystyle (b_{i})_{i\geqslant 1}}$ est la suite des nombres premiers consécutifs ${\displaystyle (p_{i})_{i\geqslant 1}}$ et la suite ${\displaystyle \pi _{i}}$ est définie par ${\displaystyle \pi _{i}=p_{i}\#}$ où ${\displaystyle p_{i}\#}$ est la primorielle du nombre ${\displaystyle p_{i}}$, c'est-à-dire le produit de tous les nombres premiers de 2 jusqu'à ${\displaystyle p_{i}}$.

Ce système a les caractéristiques suivantes :

Caractéristiques du système primoriel

Rang i	0	1	2	3	...	i	...
Poids du rang	1	2	${\displaystyle 2\times 3=6}$	${\displaystyle 2\times 3\times 5=30}$	...	${\displaystyle p_{i}\#}$	...
Valeur max de ${\displaystyle a_{i}}$	${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 4}$	${\displaystyle 6}$	...	${\displaystyle p_{i+1}-1}$	...
Valeur max de N	${\displaystyle 1}$	${\displaystyle 5}$	${\displaystyle 29}$	209	...	${\displaystyle p_{i+1}\#-1}$	...

• Base (arithmétique)
• Système de numération
• Notation positionnelle
• Produit infini de Cantor
• Forme normale de Cantor, un système de numération à base variable pour les nombres ordinaux.

• (de) Georg Cantor, « Über die einfachen Zahlensysteme », Zeitschrift für Mathematik und Physik, n^o 14,‎ 1869, p. 121-128 (lire en ligne);
• (en) Jorge M. Lopez, « A note on Cantor expansions of real numbers », sur Researchgate.net, 20 septembre 2006:
• (en) Diego Marques, « A geometric proof to Cantor’s theorem and an irrationality measure for some Cantor’s series », Annales Mathematicae et Informaticae, n^o 36,‎ 2009, p. 117-121 (lire en ligne);
• C.-A Laisant, « Sur la numération factorielle, application aux permutations », Bulletin de la S.M.F., vol. 16,‎ 1888, p. 176-183 (lire en ligne)
• (en) Donald Knuth, The Art of Computer Programming : Seminumerical Algorithms, vol. 2, Addison-Wesley, 1997 (ISBN 0-201-89684-2), p. 65-66, 208-209, 290

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	base chiffre nombre notation positionnelle numération système bibi-binaire

v · m Systèmes de numération
Arabo-indiennes	Arabe occidentale Arabe orientale Khmère (en) Indienne Mongole Thaïe
Positionnelles	À bâtons Maya Mésopotamienne Chiffres de Kaktovik (iñupiaq)
Asiatiques orientales	Chinoise Coréenne Japonaise Suzhou
Alphabétiques	Abjad Arménienne Cyrillique (en) Âryabhata (en) Éthiopienne Hébraïque Grecque Gotique
Additives	Attique (en) Brahmi Champs d’urnes Égyptienne Étrusque Forestière Inuite Romaine Tchouvache
Voir aussi : Notation musicale Système d’écriture

• Portail des mathématiques