Base de numération factorielle

Publié le 15/02/17

1. Numération décimale et numération factorielle

On note {\mathcal F} l’ensemble des suites d’entiers {(b_n)_{n\ge1}} telles que :

  • {b_1\in\mathbb{Z}}, mais {b_n\in\{0,\ldots,n-1\}} pour {n\ge2}
  • Pour tout {n\ge1}, il existe {m\ge n} tel que {b_m\lt n-1}

On va voir que : {\forall x\in\mathbb{R},\;\exists!\,(b_n)\in{\mathcal F},\;x=\displaystyle\sum_{n=1}^{+\infty}\dfrac{b_n}{n!}}
On notera {x=(b_1,b_2,\ldots,b_n,\ldots)_{\mathcal{F}}}.
Classiquement : {\text{e}=\exp(1)=2+\displaystyle\sum_{k=2}^{+\infty}\dfrac{1}{k!}=(2,1,1,\ldots,1,\ldots)_{\mathcal{F}}}.

On peut comparer ce développement avec la représentation décimale.

Notons en effet {\mathcal D} l’ensemble des suites d’entiers {(d_n)_{n\ge1}} telles que :

  • Pour tout {n\ge2}, {d_n\in\{0,\ldots,9\}}, mais {d_1} est quelconque dans {\mathbb{Z}}.
  • Pour tout {n\ge1}, il existe {m\ge n} tel que {d_m\lt 9}.

On sait qu’on a une unique écriture {x=\displaystyle\sum_{n=1}^{+\infty}\dfrac{d_n}{10^{n-1}}}, où {(d_n)_{n\ge1}\in{\mathcal D}}.

Plus précisément : {d_1=[x]} et, {\forall n\ge2,\;d_n=[10^{n-1}x]\mod 10}.

L’écriture décimale utilise la base fixe {d=10} (et on décompose sur les {1/10^n}) alors que l’écriture {x=(b_1,b_2,\ldots,b_n,\ldots)_{\mathcal{F}}} utilise une « base » variable {1,2,3,\ldots}, et on décompose sur les {1/n!}

2. Décomposition d’une réel en base factorielle

Soit {(b_n)_{n\ge1}} un élément de \mathcal{F}.

La convergence de {\displaystyle\sum_{k\ge1}\dfrac{b_k}{k!}} est immédiate car {0\le\dfrac{b_k}{k!}\lt \dfrac1{(k-1)!}} pour {k\ge2}.
Soit x=\displaystyle\sum_{k=1}^{+\infty}\dfrac{b_k}{k!}. Pour {n\ge0}, soit {x_n=\displaystyle\sum_{k=1}^{n}\dfrac{b_k}{k!}\;} et {\;r_n=\displaystyle\sum_{k=n+1}^{+\infty}\dfrac{b_k}{k!}}.

  • Montrons d’abord la connaissance de x détermine entièrement les b_n.

    Pour tout {n\ge1}, on a {0\le r_n\lt \displaystyle\sum_{k=n+1}^{+\infty}\dfrac{k-1}{k!}}
    Ainsi {0\le r_n\lt \displaystyle\sum_{k=n+1}^{+\infty}\Bigl(\dfrac{1}{(k-1)!}-\dfrac{1}{k!}\Bigr)=\dfrac{1}{n!}}.

    L’inégalité stricte est justifiée car il existe {k>n} tel que {b_k\lt k-1}.

    La relation {x=b_1+r_1} et {0\le r_1\lt 1} donne {b_1=[x]}.

    Pour n\ge2, {x=x_{n-1}+\dfrac{b_n}{n!}+r_n}. Ainsi {n!\,x=n!\,x_{n-1}+b_n+n!\,r_n}.

    Clairement : {n!x_{n-1}=n\,\Bigl((n-1)!\displaystyle\sum_{k=1}^{n-1}\dfrac{b_k}{k!}\Bigr)} est entier divisible par {n}.

    Puisque {0\le n!\,r_n\lt 1}, on en déduit {[n!\,x]=n!\,x_{n-1}+b_n}.

    On trouve donc finalement {b_n=[n!\,x]\!\mod\!n}, pour tout {n\ge2}.

  • Réciproquement, soit x\in\mathbb{\mathbb{R}}, et les b_n définis comme précédemment.

    Autrement dit {b_1=[x]} et : {\forall\, n\ge2, b_n=[n!\,x]\!\mod\!n}.

    Bien sûr {b_1} est dans {\mathbb{Z}} et : {\forall n\ge2,\; b_n\in[\![0,n-1]\!]}.

    Posons {x_n=\displaystyle\sum_{k=1}^{n}\dfrac{b_k}{k!}} et {r_n=\displaystyle\sum_{k=n+1}^{+\infty}\dfrac{b_k}{k!}}.

    Pour {n\ge2}, soit {\alpha_n=[n!x]} et {\alpha_n=nq_n+b_n} sa division par {n}.

    Pour tout {n\ge2}, on a successivement:
    {\begin{array}{rl}\alpha_n&\le n!x\lt \alpha_n+1\\\\&\Rightarrow nq_n+b_n\le n!x\lt nq_n+b_n+1\\\\&\Rightarrow q_n\le q_n+\dfrac{b_n}{n}\le (n-1)!\,x \lt q_n+\dfrac{b_n+1}{n}\le q_n+1\\\\&\Rightarrow q_n\le (n-1)!\,x\lt q_n+1\Rightarrow q_n=[(n-1)!\,x]\end{array}}
    Ainsi : {\forall n\ge2,\;\dfrac{b_n}{n!}=\dfrac{\alpha_n-nq_n}{n}=\dfrac{[n!\,x]}{n!}-\dfrac{[(n-1)!\,x]}{(n-1)!}}

    On en déduit, pour {n\ge2} (le résultat final vaut aussi si {n=1}):
    {\begin{array}{rl}\forall\, n\ge 2,\; x_n&=[x]+\displaystyle\sum_{k=2}^{n}\dfrac{b_n}{n!}\\\\&=[x]+\displaystyle\sum_{k=2}^{n}\Bigl(\dfrac{[k!\,x]}{k!}-\dfrac{[(k-1)!\,x]}{(k-1)!}\Bigr)\\\\&=[x]+\dfrac{[n!\,x]}{n!}-[x]=\dfrac{[n!\,x]}{n!}\end{array}}Pour {n\ge1}, on a {\;n!\,x-1\lt [n!\,x]\le n!\,x\;} donc {\;x-\dfrac1{n!}\lt x_n\le x}.

    Ainsi {x_n} est une valeur approchée de {x} par défaut à {\dfrac{1}{n!}} près.

    On a obtenu {\displaystyle\lim\limits_{n\rightarrow\infty}x_n=x}, ce qui prouve {x=\displaystyle\sum_{n=1}^{+\infty}\dfrac{b_n}{n!}}.

    Il reste à vérifier qu’on n’a jamais {b_n=n-1} à partir d’un certain rang.

    Supposons au contraire {b_n=n-1} pour tout {n>p}. Alors :
    {\begin{array}{rl}r_p&=\displaystyle\sum_{n=p+1}^{+\infty}\dfrac{b_n}{n!}=\displaystyle\sum_{n=p+1}^{+\infty}\dfrac{n-1}{n!}\\\\&=\displaystyle\sum_{n=p+1}^{+\infty}\Bigl(\dfrac{1}{(n-1)!}-\dfrac{1}{n!}\Bigr)=\dfrac{1}{p!}\end{array}}On en déduit : {x=\displaystyle\sum_{n=1}^{p}\dfrac{b_n}{n!}+\dfrac{1}{p!}}.

    Ainsi {p!\,x} est entier, donc {(p+1)!x} est entier multiple de {p+1}.

    Il en résulte {b_{p+1}=[(p+1)!x]\mod(p+1)=0} : contradiction!

On a ainsi prouvé l’existence et l’unicité du développement d’une réel x quelconque dans la base de numéation factorielle

3. Conversion factoriel \Rightarrow décimal

On veut calculer {x_n=\displaystyle\sum_{k=1}^{n}\dfrac{b_k}{k!}} à partir de {B=[b_1,\ldots,b_n]}.

Pour cela, on utilise un schéma de Horner. En effet:
{\begin{array}{rl}x_n&=\Bigl(\Bigl(\cdots\Bigl(\Bigl(\Bigl(\dfrac{b_n}{n}+b_{n-1}\Bigr)\dfrac{1}{n-1}+b_{n-2}\Bigr)\dfrac{1}{n-2}\\\\&\qquad+b_{n-3}\Bigr)\dfrac{1}{n-3}+\cdots\Bigr)\dfrac13+b_2\Bigr)\dfrac12+b_1\end{array}}
Pour calculer {x_n}, on commence par l’initialiser à {0}.

On ensuite : {x_n\leftarrow \dfrac{x_n}{k+1}+B[k]}, de {k=n} à {k=1}, avec un « pas » de {-1}.

Voici donc la fonction todec :

On va utiliser cette fonction pour calculer les premiers chiffres de {\text{e}}.

Pour cela, on pose B=[2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] (quinze fois le chiffre 1).

On applique la fonction todec aux {k} premiers chiffres du tableau {B}, et à la fin on compare avec l’approximation décimale de e (connue dans Numpy) :

4. Conversion décimal \Rightarrow factoriel

On suppose que {x=\displaystyle\sum_{n=1}^{+\infty}\dfrac{b_n}{n!}}.

On se propose de former {B=[b_1,b_2,\ldots,b_n]} connaissant x et n.

On remplit le tableau des {b_k}, avec {b_0=[x]} et {b_{k-1}=[k!x]\mod k} si {k\ge2}.

Voici la fonction tofact.

Sur l’exemple ci-dessous, on forme la décomposition de {\text{e}}, ou plus exactement de son approximation décimale fournie par Numpy. Il n’est donc pas étonnant que les coefficients diffèrent de {1} au bout d’un certain temps.