Votre navigateur n'accepte pas le Javascript. La navigation sur ce site risque de ne pas fonctionner correctement.

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$, 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.

10/09/2021 - Capture decran 2021 09 10 a 20.34.31

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.

10/09/2021 - Capture decran 2021 09 10 a 20.49.47

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.$

10/09/2021 - Capture decran 2021 09 10 a 21.28.14

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.$

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !

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.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.