157. Construisez une suite qui converge vers la racine carrée entière d’un nombre entier

Soit $N$ un entier naturel strictement positif.

Inspirez-vous de la suite de Héron définie par $u_0 =N$ et $\forall n\in\N, u_{n+1} = \frac{u_n+\frac{N}{u_n}}{2}$ qui converge vers $\sqrt{N}.$

L’objectif ici est de trouver la racine carrée entière de $N\comma$ autrement dit l’unique nombre entier $m$ tel que $m^2\leq N \lt (m+1)^2.$

Utilisez la partie entière

Pour tout nombre réel $x\comma$ vous appelez partie entière de $x$ l’unique nombre entier $n$ tel que $n\leq x \lt n+1.$

Ce nombre sera noté $\lfloor x \rfloor$ dans la suite.

Définissez la suite

Vous définissez la suite $u$ par $u_0 = N$ et $\forall n\in\N, u_{n+1}=\left\lfloor \frac{u_n+\left\lfloor \frac{N}{u_n}\right\rfloor}{2}\right\rfloor\comma$ avec l’idée de transformer toutes les fractions rencontrées par des nombres entiers.

Étudiez un exemple avec la racine carrée entière de $200$

Posez $N = 200.$

Partez de $u_0 = 200.$

Puis :

\begin{align*} u_{1}&=\left\lfloor \frac{u_0+\left\lfloor \frac{N}{u_0}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{200+\left\lfloor \frac{200}{200}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{200+1}{2}\right\rfloor\\ &=100. \end{align*}

\begin{align*} u_{2}&=\left\lfloor \frac{u_1+\left\lfloor \frac{N}{u_1}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{100+\left\lfloor \frac{200}{100}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{102}{2}\right\rfloor\\ &=51. \end{align*}

\begin{align*} u_{3}&=\left\lfloor \frac{u_2+\left\lfloor \frac{N}{u_2}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{51+\left\lfloor \frac{200}{51}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{51+3}{2}\right\rfloor\\ &=27. \end{align*}

\begin{align*} u_{4}&=\left\lfloor \frac{u_3+\left\lfloor \frac{N}{u_3}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{27+\left\lfloor \frac{200}{27}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{27+7}{2}\right\rfloor\\ &=17. \end{align*}

\begin{align*} u_{5}&=\left\lfloor \frac{u_4+\left\lfloor \frac{N}{u_4}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{17+\left\lfloor \frac{200}{17}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{17+11}{2}\right\rfloor\\ &=14. \end{align*}

\begin{align*} u_{6}&=\left\lfloor \frac{u_5+\left\lfloor \frac{N}{u_5}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{14+\left\lfloor \frac{200}{14}\right\rfloor}{2}\right\rfloor\\ &=\left\lfloor \frac{14+14}{2}\right\rfloor\\ &=14. \end{align*}

Ainsi la suite semble être décroissante, et même stationnaire à partir du rang $5.$

Comme $14^2 = 196$ et $15^2 = 225$ vous observez qu’effectivement $14^2 \leq 200 \lt 15^2$ et donc $14$ est bien la racine carrée entière de $200.$

Attention aux fausses conjectures

Il est tentant de noter $f$ la fonction définie sur $\R_{+}^{*}$ par $\forall x\in\R_{+}^{*}, f(x) = \left\lfloor \frac{x+\left\lfloor \frac{200}{x}\right\rfloor}{2}\right\rfloor$ et de penser que $f$ est croissante sur $[\sqrt{200}, +\infty[.$

Mais cela est inexact. Quand $x$ est proche de $\sqrt{200}$ les choses se corsent, comme le montre la courbe ci-dessous.

Les calculs suivants le confirment.

\begin{align*} f(15) &= \left\lfloor \frac{15+\left\lfloor \frac{200}{15}\right\rfloor}{2}\right\rfloor\\ &= \left\lfloor \frac{15+13}{2}\right\rfloor\\ &=14. \end{align*}

\begin{align*} f(15{,}5) &= \left\lfloor \frac{15{,}5+\left\lfloor \frac{200}{15{,}5}\right\rfloor}{2}\right\rfloor\\ &= \left\lfloor \frac{15{,}5+12}{2}\right\rfloor\\ &=13. \end{align*}

Faites une restriction sur l’ensemble de départ

Soit $m$ l’unique entier tel que $m^2 \leq 200 \lt (m+1)^2.$

Vous allez considérer $f$ la fonction définie sur $I = [m, +\infty[ \cap \N$ par $\forall n\in I, f(n) = \left\lfloor \frac{n+\left\lfloor \frac{200}{n}\right\rfloor}{2}\right\rfloor.$ Alors $f$ a l’air d’être croissante sur $I.$

Cela est suggéré par le graphique ci-dessous.

Vous pouvez alors penser que ce résultat subsiste pour d’autres valeurs de $N\comma$ mais il reste encore un problème.

Représentez graphiquement la fonction lorsque $N = 48$

La racine entière de $48$ est $6$ puisque $6^2\leq 48 \lt 7^2.$

Ci-dessous, voici la représentation graphique de la fonction $f$ définie sur $I = [6,+\infty[\cap \N$ par $\forall x\in I, f(x) =\left\lfloor \frac{x+\left\lfloor \frac{48}{x}\right\rfloor}{2}\right\rfloor.$

Vous avez $f(6)=7\comma$ $f(7)=6$ et $f(8)=7.$ La fonction $f$ n’est donc ni croissante ni décroissante.

Définissez la bonne suite

Afin d’assurer sa convergence, vous allez forcer le caractère décroissant et ce, dans la définition de la suite. Si $f(u_n)$ est meilleur que $u_n$ (au sens où $f(u_n) \lt u_n$), vous allez garder la valeur de $f(u_n).$

Soit $N$ un entier supérieur ou égal à $1.$ Voici une suite qui convient pour trouver la racine carrée entière de $N.$

Pour simplifier les notations, définissez la fonction $f$ sur $\N^{*}$ par $\forall n\in\N^{*}, f(n) =\left\lfloor \frac{n+\left\lfloor \frac{N}{n}\right\rfloor}{2}\right\rfloor.$

Définissez la suite $u$ par $u_0 = N$ et :

\forall n\in\N, u_{n+1}=\begin{cases} f(u_n) \quad\text{ si } f(u_n) \lt u_n\\ u_n \quad\text{ si } f(u_n) \geq u_n.\\ \end{cases}

Vous pouvez alors prouver que la suite $u$ est convergente (stationnaire à partir d’un certain rang) et que sa limite est précisément égale à la racine carrée entière de l’entier $N.$