Système de numération à base double

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 :
${\displaystyle 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 ${\displaystyle n}$ en base double (2,3) est donné par la fonction récursive suivante :
${\displaystyle f(0)=1}$
Pour ${\displaystyle n\geqslant 1}$, ${\displaystyle 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]
Voir la suite A062051 de l'OEIS.

• Portail des mathématiques