Numération à bases mixtes

Un système de numération à bases mixtes, dit aussi à bases de Cantor, ou encore à base variable, 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.

Principe général

Cas d'un entier

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

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

• $a_{k}\neq 0$
• pour tout $i$, $a_{i}<b_{i+1}$
• $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}$

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

Principe de démonstration

Unicité : L'écriture de $N_{0}=\sum _{i=0}^{k}a_{i}\pi _{i}$, où $0\leq a_{i}<b_{i+1}$ sous la forme

$N_{0}=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)$

met en évidence que

$a_{0}$ et $N_{1}=a_{1}+b_{2}\left(a_{2}+b_{3}\left(a_{3}+\cdots a_{k}b_{k}\right)\right)$ sont nécessairement respectivement le reste et le quotient de $N_{0}$ dans la division euclidienne par $b_{1}$

$a_{1}$ et $N_{2}=a_{2}+b_{3}\left(a_{3}+\cdots a_{k}b_{k}\right)$ sont nécessairement respectivement le reste et le quotient de $N_{1}$ dans la division par $b_{2}$

et ainsi de suite.

Existence : Soit $N$ un entier non nul. On définit les suites $a_{i}$ et $N_{i}$ en posant

• $N_{0}=N$
• pour tout $i$, $a_{i}$ et $N_{i+1}$ sont le reste et le quotient de la division de $N_{i}$ par $b_{i+1}$

On montre alors par récurrence que

pour tout $j$, $N=\sum _{i=0}^{j}a_{i}\pi _{i}+\pi _{j+1}N_{j+1}$

La suite $(N_{i})$ étant une suite d'entiers strictement décroissante tant que $N_{i}$ est non nul, elle finit par atteindre 0. Soit $k$ le premier entier tel que $N_{k+1}$ soit nul. Alors on sait que

• $a_{k}$ est non nul
• pour tout $i$, $a_{i}<b_{i+1}$
• $N=\sum _{i=0}^{k}a_{i}\pi _{i}$

 

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

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

Caractéristiques du système

Rang i	0	1	2	3	...	k	...
Poids du rang	1	$b_{1}$	$b_{1}b_{2}$	$b_{1}b_{2}b_{3}$	...	$\pi _{k}$	...
Valeur max de $a_{i}$	$b_{1}-1$	$b_{2}-1$	$b_{3}-1$	$b_{4}-1$	...	$b_{k+1}-1$	...
Valeur max de N	$b_{1}-1$	$b_{1}b_{2}-1$	$b_{1}b_{2}b_{3}-1$	$b_{1}b_{2}b_{3}b_{4}-1$	...	$\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 $b_{i}$ pouvant dépasser 10, l'écriture des $a_{i}$ risque de nécessiter d'autres chiffres que 0, 1, 2, ..., 9. D'autre part, les $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 $a_{i}$ en décimal et en insérant un séparateur entre chaque «chiffre». Ainsi, si

$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

$N=4;5;13;15;50.$

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

$N$ = 4 semaines, 5 jours, 13 heures, 15 minutes, 50 secondes.

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

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

En 1869, Georg Cantor a prouvé 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 $(\pi _{i})$ est une suite strictement croissante d'entiers naturels, pour que, pour tout entier $N$ non nul, il existe toujours un entier $k$ et $k+1$ entiers $a_{0},a_{1},\cdots ,a_{k}$ uniques tels que

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

il est nécessaire et suffisant que

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

Cas d'un réel compris entre 0 et 1

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

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

• pour tout $i$, $a_{i}<b_{i}$
• $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 $x\pi _{i}$ n'est jamais entier. S'il existe $k$ tel que $x\pi _{k}$ est entier, $x$ possède deux décompositions, une telle que, pour tout $i>k$, $a_{i}=0$, l'autre pour laquelle pour tout $i>k$, $a'_{i}=b_{i}-1$.

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

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

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

Critère d'irrationalité

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

Cas d'une base périodique

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

Exemples

Métrologie

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

Rang i	0	1	2	3	4	5
Poids du rang	1	10	60	120	1200	7200
Valeur max de $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 $b_{i}$ valent 20 à l'exception de $b_{2}$ qui vaut 18.

Numération factorielle

Dans ce système, la suite des $(b_{i})_{i\geq 1}$ est la suite des entiers consécutifs à partir de 2, et la suite $\pi _{i}$ est définie par $\pi _{i}=(i+1)!$ où $(i+1)!$ est la factorielle du nombre $i+1$, c'est-à-dire le produit de tous les entiers de 1 jusqu'à $(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	$2\times 3=6$	$2\times 3\times 4=24$	...	$(i+1)!$	...
Valeur max de $a_{i}$	$1$	$2$	$3$	$4$	...	$i+1$	...
Valeur max de N	$1$	$5$	$23$	$119$	...	$(i+2)!-1$	...

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

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

et un réel $x$ s'écrit

$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, $e=2+\sum _{i=1}^{+\infty }{\frac {1}{(i+1)!}}$ a tous ses coefficients $a_{i}$ égaux à 1.

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

Numération primorielle

Dans ce système, la suite des $(b_{i})_{i\geqslant 1}$ est la suite des nombres premiers consécutifs $(p_{i})_{i\geqslant 1}$ et la suite $\pi _{i}$ est définie par $\pi _{i}=p_{i}\#$ où $p_{i}\#$ est la primorielle du nombre $p_{i}$, c'est-à-dire le produit de tous les nombres premiers de 2 jusqu'à $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	$2\times 3=6$	$2\times 3\times 5=30$	...	$p_{i}\#$	...
Valeur max de $a_{i}$	$1$	$2$	$4$	$6$	...	$p_{i+1}-1$	...
Valeur max de N	$1$	$5$	$29$	209	...	$p_{i+1}\#-1$	...

Voir aussi

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

Bibliographie

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