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.

Principe général

Cas d'un entier

Soit $(b_{i})_{i ⩾ 1}$ une suite d'entiers strictement supérieurs à 1. On construit la suite $(π_{i})_{i ⩾ 0}$ en posant $π_{0} = 1$ et pour tout $i$ , $π_{i + 1} = π_{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}, \dots, a_{k}$ tels que

$a_{k} \neq 0$
pour tout $i$ , $a_{i} < b_{i + 1}$
$N = \sum_{i = 0}^{k} a_{i} π_{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} (a_{1} + b_{2} (a_{2} + b_{3} (a_{3} + \dots + a_{k} 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}$ .

Modèle:Boîte déroulante/début Unicité : L'écriture de $N_{0} = \sum_{i = 0}^{k} a_{i} π_{i}$ , où $0 \leq a_{i} < b_{i + 1}$ sous la forme

N_{0} = a_{0} + b_{1} (a_{1} + b_{2} (a_{2} + b_{3} (a_{3} + \dots + a_{k} b_{k})))

met en évidence que

a_{0}

et

N_{1} = a_{1} + b_{2} (a_{2} + b_{3} (a_{3} + \dots a_{k} b_{k}))

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} (a_{3} + \dots a_{k} b_{k})

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} π_{i} + π_{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} π_{i}$

Modèle:Boîte déroulante/fin

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 Modèle:Formule	0	1	2	3	...	k	...
Poids du rang	1	$b_{1}$	$b_{1} b_{2}$	$b_{1} b_{2} b_{3}$	...	$π_{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$	...	$π_{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 = 50 + 15 \times 60 + 13 \times 60 \times 60 + 5 \times 60 \times 60 \times 24 + 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^[3], c'est-à-dire $b_{i + 1}$ :

N = 4_{\infty} 5_{7} 1 3_{24} 1 5_{60} 5 0_{60} .

En 1869, Georg Cantor a prouvéModèle:Sfn 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 $(π_{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}, \dots, a_{k}$ uniques tels que

N = \sum_{i = 0}^{k} a_{i} π_{i}

il est nécessaire et suffisant que

$π_{0} = 1$
pour tout $i$ , $π_{i + 1}$ soit un multiple de $π_{i}$ , i.e. $π_{i + 1} = π_{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 ⩾ 1}$ une suite d'entiers strictement supérieurs à 1. On construit la suite $(π_{i})_{i ⩾ 0}$ en posant $π_{0} = 1$ et pour tout $i$ , $π_{i + 1} = π_{i} \times b_{i + 1}$ .

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

pour tout $i$ , $a_{i} < b_{i}$
$x = \sum_{i = 1}^{+ \infty} \frac{a_{i}}{π_{i}} = \frac{a_{1}}{b_{1}} + \frac{a_{2}}{b_{1} b_{2}} + \dots$

De plus cette décomposition est unique dès que $x π_{i}$ n'est jamais entierModèle:Sfn. S'il existe $k$ tel que $x π_{k}$ est entier, $x$ possède deux décompositionsModèle:Sfn, 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 posantModèle:Sfn

$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} \dots b_{i}}$ a pour développement de Engel $] b_{1}, b_{2}, b_{3}, . . . [$ .

Critère d'irrationalité

Soit $(b_{i})_{i ⩾ 1}$ une suite d'entiers strictement supérieurs à 1 et la suite $π_{i} = \prod_{j = 1}^{i} b_{j}$ . On suppose que, pour tout entier $q$ , $q$ divise les $π_{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 ⩾ 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 Modèle:Sfn. 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 ⩾ 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 irrationnelModèle:Sfn.

Cas d'une base périodique

Si la suite $(b_{i})_{i ⩾ 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 rangModèle:Sfn.

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 Modèle:IVe et Modèle:IIIe 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^[4]
Rang Modèle:Formule	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^[5].

Numération factorielle

Modèle:Article détaillé 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 $π_{i}$ est définie par $π_{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 Modèle:Formule	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} + 2 a_{1} + 6 a_{2} + . . . + (k + 1)! a_{k}$

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

$x = ⌊ x ⌋ + \sum_{i = 1}^{+ \infty} \frac{a_{i}}{(i + 1)!} = ⌊ x ⌋ + \frac{a_{1}}{2} + \frac{a_{2}}{6} + \dots$

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 factorielleModèle:Sfn.

Numération primorielle

Dans ce système, la suite des $(b_{i})_{i ⩾ 1}$ est la suite des nombres premiers consécutifs $(p_{i})_{i ⩾ 1}$ et la suite $π_{i}$ est définie par $π_{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 Modèle:Formule	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.

Références

Modèle:Références

Bibliographie

Modèle:Palette Modèle:Portail

↑ Modèle:Lien web, diapo 3
↑ Modèle:Ouvrage
↑ Seth J. Chandler, "Mixed Radix Number Representations", Wolfram Demonstrations Project, March 7 2011
↑ Modèle:Chapitre, p.118
↑ Modèle:Lien web, p.5

[1] Modèle:Lien web, diapo 3

[2] Modèle:Ouvrage

[3] Seth J. Chandler, "Mixed Radix Number Representations", Wolfram Demonstrations Project, March 7 2011

[4] Modèle:Chapitre, p.118

[5] Modèle:Lien web, p.5

[1]

[2]

[3]

[4]

[5]

Numération à bases mixtes

Sommaire

Principe général

Cas d'un entier

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

Critère d'irrationalité

Cas d'une base périodique

Exemples

Métrologie

Numération factorielle

Numération primorielle

Voir aussi

Références

Bibliographie

Menu de navigation

Numération à bases mixtes

Principe général

Cas d'un entier

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

Critère d'irrationalité

Cas d'une base périodique

Exemples

Métrologie

Numération factorielle

Numération primorielle

Voir aussi

Références

Bibliographie

Menu de navigation

Rechercher