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.$
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !