Forum Prepas.org

Nous avons f(x)= x+1 et g(x)=$ \frac{x}{x+1} $
Notons $ u_{n} $ la valeur du numérateur à la n-ème étape et $ v_{n} $ celle du dénominateur.
On a donc x=$ \frac{u_{n}}{v_{n}} $
Si on applique (je sais pas quel mot convient, désolé) la fonction f à x, on obtient $ u_{n+1}=u_{n}+v_{n} $ et $ v_{n+1}=v_{n} $ et si on applique la fonction g à x, on obtient $ u_{n+1}=u_{n} $ et $ v_{n+1}=u_{n}+v_{n} $
$ $

On cherche à obtenir $ u_{n} $=7891 et $ v_{n} $=1987

Or, on remarque que 7891 = 3*1987 + 1930 donc si l'on a $ u_{k} $=1930 et $ v_{k} $=1987, après avoir appliqué 3 fois la fonction f(x) on aboutit au résultat voulu.
On peut réitérer ce résultat plusieurs fois avec l'algorithme d'Euclide qui nous donne :
7891 = 3*1987 + 1930
1987 = 1*1930 + 57
1930 = 33*57 + 49
57 = 1*49 + 8
49 = 6*8 + 1
8 = 7*1 + 1 (je ne mets pas 0 comme dans un algorithme d'Euclide classique simplement car $ u_{0} $=$ v_{0} $=1)

Ainsi, en remontant l'algorithme d'Euclide on applique la fonction g k fois (avec k le nombre qui multiplie le reste de la ligne du dessus) et on "change" de fonction à chaque fois que l'on doit changer de ligne. On applique donc g 7 fois, ce qui nous donne $ \frac{1}{8} $. Ensuite, on effectue f 6 fois, on obtient $ \frac{49}{8} $, puis g une fois ($ \frac{49}{57} $, puis f 33 fois ($ \frac{1930}{57} $, puis g une fois ($ \frac{1930}{1987} $) et enfin f trois fois ce qui nous permet d'aboutir au résultat : $ \frac{7891}{1987} $.

Petit complément : on remarque donc que l'on peut exprimer toutes les fractions dont le dénominateur et le numérateur sont premiers entre eux (condition pour l'algorithme d'Euclide), soit pour toutes les fractions irréductibles soit pour l'ensemble des nombres rationnels.

Pour la première :

$ A_{x}=\int_{0}^{x}E(t)dt $
$ = \sum_{i=1}^{E(x)}\int_{i-1}^{i}(i-1)dt + \int_{E(x)}^{x}E(t)dt $
$ = \sum_{i=1}^{E(x)}(i-1) + E(x)*(x-E(x)) $
$ = \sum_{i=0}^{E(x)-1}i + E(x)*(x-E(x)) $
$ = \frac{(E(x)-1)(E(x)-1+1)}{2} + E(x)*(x-E(x)) $
$ = E(x)*(\frac{(E(x)-1)}{2} + (x-E(x))) $
$ = E(x)*(\frac{(2x-E(x)-1)}{2}) $

Pour la deuxième :

Notons n le plus grand entier tel que $ \frac{\ln n}{\ln 2} \leq x $ (soit $ \log_{2} (n) \leq x $)

On a donc $ n\leq 2^{t}<n+1 \Leftrightarrow \log_{2} (n) \leq t< \log_{2} (n+1) $

$ B_{x}=\int_{0}^{x}E(2^{t})dt $

$ = \sum_{i=2}^{n}\int_{\log_{2} (i-1)}^{\log_{2} (i)}E(2^{t})dt + \int_{\log_{2} (n)}^{x}E(2^{t})dt $

$ = \sum_{i=2}^{n}\int_{\log_{2} (i-1)}^{\log_{2} (i)}idt + \int_{\log_{2} (n)}^{x}ndt $

$ = \sum_{i=2}^{n}i(\log_{2} (\frac{i}{i-1})) + n(x-\log_{2} (n)) $

$ = \sum_{i=2}^{n}i(\log_{2} (i) - \log_{2} (i-1)) + n(x-\log_{2} (n)) $

$ = \sum_{i=2}^{n}i\log_{2} (i) - \sum_{i=2}^{n}i\log_{2} (i-1) + n(x-\log_{2} (n)) $

$ = n\log_{2}(n) + \sum_{i=2}^{n-1}i\log_{2} (i) - \sum_{i=1}^{n-1}(i+1)\log_{2}(i) + n(x-\log_{2} (n)) $

$ = n\log_{2}(n) + \sum_{i=2}^{n-1}i\log_{2} (i) - \sum_{i=2}^{n-1}i\log_{2}(i) - 1\log(1) - \sum_{i=1}^{n-1}\log_{2}(i) + n(x-\log_{2} (n)) $

$ = - \sum_{i=1}^{n-1}\log_{2}(i) + nx $

$ = - \log(n-1)! + nx $

Voilà, pour $ B_{x} $ il y a probablement une simplification qui rend ce résultat plus "beau", mais je ne l'ai pas trouvée x) si jamais elle est accessible niveau TS, je veux bien un indice

EDIT : Simplification faite