Système de numération à base double

Étant donné deux entiers positifs premiers entre eux p et q, le système de numération à base double (double-base number system en anglais) est un système de représentation dans lequel chaque entier positif n'est représenté comme somme de {p,q}-entiers, c.à.d., d'entiers de la forme pⁱq^j :
$n=\sum _{i,j}d_{i,j}p^{i}q^{j}$
avec $d_{i,j}$ = 0 ou 1, et i,j entiers positifs[1].

Ceci est une définition non-signée, mais il existe aussi une définition signée autorisant les termes négatifs, où $d_{i,j}$ peut prendre également la valeur -1[2].

Non-unicité de la représentation

Contrairement aux bases simples, une base double ne garantit pas l'unicité de l'écriture d'un nombre. Par exemple, le nombre 127 possède 783 représentations différentes dans la base double {2,3}, parmi lesquelles :
$127=2^{2}3^{3}+2^{1}3^{2}+2^{0}3^{0}=2^{2}3^{3}+2^{4}3^{0}+2^{0}3^{1}=2^{5}3^{1}+2^{0}3^{3}+2^{2}3^{0}$ [1]

Le nombre 10 possède 5 représentations différentes, 100 en possède 402, 1 000 en possède 1 295 579, , etc.[2]

On parle de représentation canonique lorsque le nombre de termes de la somme est le plus petit possible. Ci-dessus, les 3 seules représentations canoniques du nombre 127. Il n'existe pas de représentation à moins de 3 termes pour 127[1].

Le nombre de représentations non-signées d'un entier $n$ est donné par la fonction récursive suivante :
$f(1)=1$
Pour $n\geq 1$ , $f(n)={\begin{cases}f(n-1)+f(n/3),&{\text{si }}n\equiv 0{\pmod {3}}\\f(n-1),&{\text{sinon.}}\end{cases}}$ [2]

Références

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.