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$, autrement dit l’unique nombre entier $m$ tel que $m^2\leq N < (m+1)^2.$

Utilisez la partie entière

Pour tout nombre réel $x$, on appelle partie entière de $x$ l’unique nombre entier $n$ tel que $n\leq x < 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$, avec l’idée de transformer toutes les fractions rencontrées par des nombres entiers.

Etudiez 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 < 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 < (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$, 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 < 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$, $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) < 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(n) \quad\text{ si } f(u_n) < 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.$