Des milliers de décimales de e

Publié le 16/02/17

On pourra se reporter à l’article « Base de numération factorielle ».

On sait que tout {x\in\mathbb{R}} s’écrit de manière unique en « base factorielle » :
{x=\displaystyle\sum_{k=1}^{+\infty}\dfrac{b_k}{k!}\quad\text{avec les conditions}\quad \begin{cases}b_1\in\mathbb{Z}\\\forall k\ge 2,\;b_k\in[\![0,n-1]\!]\end{cases}}

Plus précisément, {b_1=[x]} et : {\forall n\ge2,\;b_n=[n!\,x]\mod n}.

On note {x=\displaystyle\sum_{k=1}^{+\infty}\dfrac{b_k}{k!}=(b_1,b_2,\ldots,b_n,\ldots)_{\mathcal{F}}} et {x_n=\displaystyle\sum_{k=1}^{n}\dfrac{b_k}{k!}=(b_1,b_2,\ldots,b_n)_{\mathcal{F}}}.

On se propose de trouver {[10^mx_n]}, avec m\in\mathbb{N}^*.

On pourrait écrire {10^mx_n=(10^m\,b_1,10^m\,b_2,\ldots,10^m\,b_n)_{\mathcal{F}}}.

Mais les entiers {10^m\,b_k} (pour {k\ge2}) ne sont en général pas dans {[[0,k-1]]}.

Il faut réduire cette écriture, par un algorithme de reports de retenues successives.

1. L’algorithme de report de retenues

L’objectif est de passer de {10^mx_n=\displaystyle\sum_{k=1}^{n}\dfrac{10^m\,b_k}{k!}} à {10^mx_n=\displaystyle\sum_{k=1}^{n}\dfrac{r_k}{k!}}.

Dans cette dernière écriture, {r_1=[10^mx_n]}, et {0\le r_k\lt k} pour {k\ge2}.

  • Soit {10^m\,b_n=q_n n+r_n} la division de {10^m\,b_n} par {n}, avec {0\le r_n\lt n}.
    {\begin{array}{rl}10^mx_n&=\displaystyle\sum_{k=1}^{n-2}\dfrac{10^m\,b_k}{k!}+\dfrac{10^m\,b_{n-1}}{(n-1)!}+\dfrac{10^m\,b_n}{n!}\\\\&=\displaystyle\sum_{k=1}^{n-2}\dfrac{10^m\,b_k}{k!}+\dfrac{10^m\,b_{n-1}}{(n-1)!}+\dfrac{q_n n+r_n}{n!}\\\\&=\displaystyle\sum_{k=1}^{n-2}\dfrac{10^m\,b_k}{k!}+\dfrac{10^m\,b_{n-1}+q_n}{(n-1)!}+\dfrac{r_n}{n!}\end{array}}La première division se traduit donc par une retenue {q_n} reportée sur {10^m\,b_{n-1}}.
  • On divise maintenant {b'_{n-1}=10^m\,b_{n-1}+q_n} par {n-1}.

    Cela s’écrit : {b'_{n-1}=q_{n-1}(n-1)+r_{n-1}}, avec {0\le r_{n-1}\lt n-1}.
    {\begin{array}{rl}10^mx_n&=\displaystyle\sum_{k=1}^{n-2}\dfrac{10^m\,b_k}{k!}+\dfrac{b'_{n-1}}{(n-1)!}+\dfrac{r_n}{n!}\\\\&=\displaystyle\sum_{k=1}^{n-3}\dfrac{10^m\,b_k}{k!}+\dfrac{10^m\,b_{n-2}+q_{n-1}}{(n-2)!}+\dfrac{r_{n-1}}{(n-1)!}+\dfrac{r_n}{n!}\end{array}}

  • On continue… À l’avant-dernière étape:
    {10^mx_n=10^m\,b_{1}+\dfrac{10^m\,b_{2}+q_{3}}{2!}+\displaystyle\sum_{k=3}^{n}\dfrac{r_k}{k!}}Il reste à diviser {b'_2=10^m\,b_{2}+q_{3}} par {2}.

    Cette division s’écrit {b'_2=2q_2+r_2}, avec {r_2\in\{0,1\}}.

    On obtient finalement, en posant {r_1=10^m\,b_{1}+q_2} :
    {\begin{array}{rl}10^mx_n&=10^m\,b_{1}+\dfrac{b'_2}{2!}+\displaystyle\sum_{k=3}^{n}\dfrac{r_k}{k!}\\&=10^m\,b_{1}+q_2+\displaystyle\sum_{k=2}^{n}\dfrac{r_k}{k!}=(r_1,r_2,\ldots,r_n)_{\mathcal{F}}\end{array}}

La conversion est terminée, avec notamment {r_1=[10^m\,x_n]}.

2. Mise en oeuvre de l’algorithme de réduction

Notons {10^mx_n=(r_1,r_2,\ldots,r_n)_{\mathcal{F}}} l’écriture réduite de {10^mx_n} dans {\mathcal{F}}.

On écrit une fonction reducb :

  • Prenant en argument {X=[b_1,b_2,\ldots,b_n]} et {m\in\mathbb{N}^*}.
  • Plaçant la liste réduite {[r_1,r_2,\ldots,r_n]} dans la même variable.

Remarque : cette méthode donne en particulier la partie entière {r_1} de {10^mx_n}.E]

Prenons un exemple. On sait que la liste X, recopiée ici dans Y, représente le nombre e (du moins une bonne approximation de celui-ci) dans la base de numération \mathcal{F} :

L’instruction suivante consiste à effectuer un produit par 10^5, et à replacer « in situ » le résultat (réduit après propagation des retenues) dans la variable Y. On voit ici le contenu modifié de Y, et on note que Y[0] contient maintenant la partie entière de 10^5\text{e}, c’est-à-dire 271828 :

La liste contenue dans Y représente maintenant une « bonne » approximation de 10^5\text{e}, comme on le voit avec la vérification suivante :

3. Calculer des milliers de décimales du nombre e

Pour {n\ge1}, posons e_n=2+\displaystyle\sum_{k=2}^{n}\dfrac{1}{k!}=(2,1,\ldots,1)_\mathcal{F}.
(dans la représentation précédente, le chiffre 1 apparaît n-1 fois).

Pour {n\ge1}, soit {v_n=n!10^{-(n+1)}}. On a {\dfrac{v_{n+1}}{v_n}=\dfrac{n+1}{10}}.

La suite {(v_n)} est donc croissante à partir de {n=9}. Or {v_{27}\approx1.09>1}.

Ainsi {\dfrac{1}{n!}\lt 10^{-(n+1)}} donc {0\lt \text{e}-e_n\lt 10^{-(n+1)}} pour {n\ge27}.

Les nombres {\text{e}} et {e_n} ont alors les mêmes {n} premières décimales.

Voici la fonction chiffres_de_e_par_paquets, qui donne {n} décimales de {\text{e}} (obtenues par tranches de {m} décimales successives, mais ça ne change pas le résultat final).

Le résultat est une chaîne, comme « 2718281828… » mis pour 2.718281828\ldots

Voici les 10 premières décimales de e (le 2ème argument n’est pas important):

Ce n’est que lorsque le nombre de décimales demandé est très important que le choix du deuxième argument devient significatif, comme on le voit sur les exemples suivants, où on a demandé 1000 décimales de e, avec (en interne) des paquets de 1000 chiffres (donc un seul paquet), ou de cent chiffres, ou de dix, ou un chiffre à la fois.

Finalement, et parce Python nous autorise à utiliser des entiers arbitrairement longs (et en particulier 10^n pour tout n), le mieux est de faire un seul paquet (donc de choisir m=n avec les notations précédentes). Dans ce cas, la fonction chiffres_de_e_par_paquets n’effectue qu’un seul passage dans la boucle. Il est alors beaucoup élégant de réécrire le tout dans une seule fonction, que voici:

Et voici les mille premières décimales de \text{e} (lire \text{e}=2.271...354) :

‘27182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101157477041718986106873969655212671546889570350354’

Bien sûr, le temps de calcul augmente quand on est très exigeant :

Dans les 100000 premières décimales de e, voici les dix dernières :