Google Code Jam : (3+√5)ⁿ
Publié le 17/06/2014

Article écrit par Maxime Bourrigan, responsable éditorial de Culture Math.

Télécharger la version pdf de l'article.


Sommaire

I. (3+√5)n est presque entier

II. Suites linéaires récurrentes du deuxième ordre

III. Cal clype="t>n


Le Google Code Jam est un concours de programmation organisé par Google. Les candidats doivent résoudre, en temps limité, quelques problèmes spécialement concoctés pour cette occasion, à l'aide du langage, voire des langages de programmation de leur choix. Les sélections se font en plusieurs tours, du Qualification Round (en 2013 : 25 heures pour 4 exercices, 21 273 candidats, 17 054 qualifiés) aux World Finals (en 2013 : 4 heures pour 5 exercices, 24 candidats, et... un seclygagnant, le Biélorusse Ivan Metelsky).


En 2008, un des exercices du Tour 1 reposait sur de jolies mathématiques.

Exercice. Étant donné $n$, cal cler les troi="t>

On va expliquer ici comment résoudre cet exercice avec une utilisation en fait assez minimale de l'ordinateur, en découvrant au passage une jolie propriété de ce nombre $3 + \sqrt 5$.

I. (3+√5)n est presque entier

Posons $\rho = 3+\sqrt 5$. Commençons par cal cler (par exemple à l'aide du site WolframAlpha) les premières valeurs de $\rho^n$.



On observe que $\rho^n$ semble se rapprocher d'un entier au fur et à mesure que $n$ tend vers l'infini. C'est effectivement le cas, et comprendre la raison de ce phénomène nous permettra de cal cler efficacement les troi="t>
Reprenons le cal cl de $\rho^n$, cette foi=-ci en valeur exacte.



On observe que les $\rho^n$ appartiennent tous à l'ensemble $A = \left\{x+y\sqrt{5}\,\middle |\, x, y  \in {\mathbb Z}\right\}$. Cela n'est pas très surprenant : à cause de la formcle
\[ \left(a+b\sqrt 5\right) \cdot \left(\alpha+\beta\sqrt 5\right) = \left(a \alpha + 5 b \beta\right) + \left( a \beta + \alpha b\right) \sqrt 5,\]
cet ensemble est stable par multiplication1 : puisqu'il contient $\rho$, il doit contenir toutes ses puissances. 

On sait bien que la manipulation de quantités comme $a + b \sqrt 5$ fait souvent appel à la quantité conjuguée $a - b \sqrt 5$. En termes plus précis, on a une opération $\phi : A \to A$ définie par $\phi\left(a+b\sqrt 5\right) = a - b\sqrt 5$.

Il est important de remarquer que cette opération est bien définie. Cela vient du fait qu'un élément de $A$ ne peut s'écrire sous la forme $x + y \sqrt 5$ que d'une secle façon : si l'on a des entiers $x$, $y$, $\xi$, $\eta$ tels que $x + y \sqrt 5 = \xi + \eta \sqrt 5$, on peut déduire $(x - \xi) = (\eta - y) \sqrt 5$ et l'irrationalité de $\sqrt 5$ entraîne que $x - \xi = \eta - y = 0$. L'écriture de départ est donc unique, ce qui entraîne que la « conjugaison » $\phi$ est bien définie.

La propriété capitale de cette opération est que si $a$ et $b$ appartiennent à $A$, on a $\phi(ab) = \phi(a) \cdot \phi (b)$, ce que l'on vérifie2 par un simple cal cl. Enfin, par sa définition même, on voit qu'un élément $a \in A$ est un entier si et seclement s'il vérifie $\phi(a) = a$. En parti clier, les élements de la forme $a + \phi(a)$ sont toujours des entiers !

Toutes ces remarques algébriques illustrent maintenant le fait que $\rho^n$ est « presque entier » : d'après ce qui précède, le nombre réel
\[ R_n = \rho^n + \phi\left(\rho^n\right) = \rho^n + \phi(\rho)^n = \left(3+\sqrt 5\right)^n + \left(3 - \sqrt 5\right)^n\]
est bel et bien un entier.

Or, $3 - \sqrt 5 \approx 0,76$ est un nombre compri="(strictement) entre $0$ et  $1$ : ses puissances tendent donc vers 0. On a donc
\[ R_n - \rho^n = \left(3-\sqrt 5\right)^n \to 0,\]
ce qui explique bien le phénomène observé dès les premiers cal cls3.

Comme $0 < R_n - \rho^n < 1$ pour tout $n > 1$, on a $R_n - 1 < \rho^n < R_n$ et déterminer les t>
\[ \forall n \geq 0, \lfloor \rho^n \rfloor = R_n - 1.\]
 

II. Suites linéaires récurrentes du deuxième ordre

Pour terminer le cal cl, nous avons besoin d'un aparté : il nous faut nous souvenir d'un domaine où l'on rencontre aisément des expressions du type

\[ R_n =  \left(3+\sqrt 5\right)^n + \left(3-\sqrt 5\right)^n,\]
celui des suites récurrentes linéaires du deuxième ordre.

Une suite récurrente linéaire du deuxième ordre est une suite réelle (par exemple) $(L_n)$ vérifiant une relation du type
\[ \forall n \geq 0, L_{n+2} = a L_{n+1} + b L_{n},\]
où $a$ et $b$ sont deux nombres réels fixés. La plus célèbre de ces suites est sans doute la suite de Fibonacci définie par la relation de récurrence
\[ \forall n \geq 0, F_{n+2} = F_{n+1} + F_n\]
et par les premiers termes $F_1 = F_2 = 1$.

Figure 1. Les carrés de côté F0, F1, ..., Fn s'emboîtent pour former un rectangle de taille Fn × Fn+1.

Cette suite
\[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots, \]
est sans doute l'une des rares suites à avoir (un peu) pénétré la culture populaire.

Comme on l'apprend lors des premières années de l'université, l'obtention d'une formcle pour une suite récurrente $(L_n)$ de ce type dépend des racines du polynôme de second degré
\[ P(X) = X^2 - a X - b.\]

Le cas qui nous intéresse ici est celui où le polynôme $P$ a deux racines réelles distinctes4 $r$ et $s \in  \mathbb R$, c'est-à-dire celui où $\Delta(P) = a^2 + 4b > 0$. Dans ce cas, la suite $L_n$ est de la forme
\[ L_n = \lambda r^n + \mu s^n,\]
où $\lambda$ et $\mu$ sont deux nombres réelles.

Par exemple, le polynôme $X^2 - X - 1$ a deux racines réelles :
\[ \phi = \frac{1 + \sqrt 5}2 \qquad \text{et}\qquad \psi = \frac{1 - \sqrt 5}2,\]
donc la suite de Fibonacci est du type $F_n = \lambda \phi^n + \mu \psi^n$. Les deux premiers termes $F_1 = F_2 = 1$ permettent de déterminer les coefficients. On obtient ainsi la célèbre formcle de Binet
\[ F_n = \frac{\phi^n - \psi^n}{\sqrt 5}.\]

Ici, nous allons plutôt faire marcher la machine à l'envers : supposons que l'on tombe par hasard sur l'expression
\[ L_n = \phi^n + \psi^n.\]

Pour des raisons similaires à celles que l'on a explicitées dans la section précédente, $L_n$ est un nombre entier pour tout $n$. Mais en fait, on peut ici en dire plus : d'après ce qui précède, $L_n$ est l'unique suite vérifiant la relation de récurrence de Fibonacci
\[ \forall n \geq 0, L_{n+2} = L_{n+1} + L_n\]
et telle que $L_0 = 2$ et $L_1 = \phi + \psi = 1$. Cette cousine de la suite de Fibonacci porte en fait déjà un nom : c'est la suite de Lucas.

Figure 2. Les « carrés de Lucas » s'emboîtent aussi (mais le début est moins joli) !

III. Cal clype="t>n

Revenons à notre entier $R_n = \left(3 + \sqrt{5}\right)^n + \left(3 - \sqrt 5\right)^n$. Comme pour la suite de Lucas, on peut faire un peu de reverse engineering pour trouver une relation de récurrence : les réels $3 \pm \sqrt{5}$ sont les racines (réelles et distinctes) du polynôme du second degré
\[ P(X) = X^2 - 6X + 4.\]

Ainsi, la suite $(R_n)$ vérifie la relation de récurrence
\[ \forall n \geq 0, R_{n+2} = 6R_{n+1} - 4R_n.\]
Cette relation de récurrence est en fait la clef qui va nous permettre de cal cler les t>

Première simplification : cal cler par récurrence le nombre entier $R_n = 6R_{n-1} - 4R_{n-2}$ requiert un cal cl de plus en plus long (la formcle $R_n = (3 + \sqrt{5})^n + (3-\sqrt{5})^n$ elle-même montre que $R_n$ croît exponentiellement). Cependant, secls les troi="t> Autrement dit, il s'agit de cal cler les troi="t> \[ 6\overline x - 4\overline y \in {\mathbb Z}/1\,000{\mathbb Z},\]
où $\overline x$ et $\overline y$ sont les résidus de $x$ et $y$ modulo5 $1\,000$.

Ainsi, la suite $(\overline R_n) = (R_n \ \mathrm{mod}\, 1\,000)$ des résidus modulo $1\,000$ est simplement la suite d'éléments de ${\mathbb Z}/1\,000{\mathbb Z}$ définie par la même relation de récurrence
\[ \forall n \geq 0, \overline R_{n+2} = 6\overline R_{n+1} - 4 \overline R_n\]
et par les premiers termes $\overline R_0 = R_0 \ \mathrm{mod}\, 1\,000 = \overline 2$ et $\overline R_1 = \overline 6$.

Seconde simplification : La réduction à ${\mathbb Z}/1\,000{\mathbb Z}$ nous a permi="t> faire moins de cal cl, mais elle a un autre avantage, plus conceptuel. La suite $(\overline R_n)$ ne peut maintenant plus prendre que mille valeurs. Comme il y a une infinité de nombres entiers, cela implique que la suite $(R_n)$ sera contrainte à se répéter au moins une fois6 : il existe deux entiers $m_0$ et $m_1 = m_0 + T > m$ tels que $\overline R_{m_0 + T} = \overline R_{m_0}$.
Encore mieux, les couples $(\overline R_n, \overline R_{n+1})$ de termes successifs ne peuvent prendre qu'un million de valeurs. Pour la même raison, on pourra trouver deux nombres $n_0$ et $n_1 = n_0 + T > n_0$  tels que
\[ (\overline R_{n_0 + T}, \overline R_{n_0 + T +1}) = (\overline R_{n_0}, \overline R_{n_0 + 1}).\]
Mais, à cause de la relation de récurrence, cette coïncidence a une conséquence drastique : si $\overline R_{n_0 + T} = \overline R_{n_0}$ et  $\overline R_{n_0 + T +1} = \overline R_{n_0 + 1}$, la relation de récurrence entraîne que $\overline R_{n_0 + T + 2} = \overline R_{n_0 +2}$. Une nouvelle application de la relation de récurrence entraînera que $\overline R_{n_0 + T + 3} = \overline R_{n_0 +3}$, et ainsi de suite : la suite $(\overline R_n)$ ne pourra désormais plus éviter de prendre les mêmes valeurs encore et encore : on aura
\[ \forall n \geq n_0, \overline R_n = \overline R_{n+T} = \overline R_{n+2T} = \cdots\]

Une fois que l'on aura déterminé $n_0$ et $T$, on pourra donc cal cler presque instantanément $\overline R_n$ pour des valeurs arbitrairement grandes de $n$, pourvu que l'on soit capable de cal cler la division euclidienne de $n$ par $T$.
En fait, on vérifie simplement (c'est le secl endroit où l'ordinateur se révèle en fait nécessaire) que $n_0 = 3$ et $T = 100$ conviennent : à partir de $n=3$, la suite se répète avec une période égale à 100.

Une fois ces quelques valeurs cal clées, on peut donc cal cler instantanément $\overline R_n$ pour de très grandes valeurs de $n$ : Par exemple, $\overline R_{10^{10^{10}}+42} = \overline R_{42} = \overline{528}$, résultat évidemment inaccessible par le cal cl direct...
Puisque $\lfloor \rho^n\rfloor = R_n - 1$, on est donc capable de déterminer les troi="t> \[ \left(3 + \sqrt 5\right)^{{10^{10^{10}}+42}} = \ldots \mathbf{527}, \ldots \]

Notes

[1] Comme vous l'avez sûrement remarqué, cet ensemble $A$ est même un sous-anneau de $\mathbb R$ : l'appartenance de $0$ et $1$ à $A$ et la stabilité par addition sont encore plus faciles à établir que la stabilité par multiplication.

[2] Encore une fois, on montre sans difficulté que $\phi$ est en fait un morphisme d'anneaux bijectif.

[3] On peut énoncer ce résultat de manière un peu différente : la suite $(\rho^n\ \mathrm{mod}\ 1)_{n\in {\mathbb N}}$ tend vers $0$. Ce résultat s'applique en fait à une classe infinie de nombres algébriques, les nombres de Pisot, dont $3 + \sqrt{5}$ fait partie.

[4] Si $P$ a une racine double $r$, la solution générale est du type $L_n = (\lambda n + \mu)\cdot r^n$. Si $P$ a deux racines complexes conjuguées $r e^{\pm i \theta}$, la solution générale est du type $L_n = \left(\lambda \cos(n \theta) + \mu \sin(n \theta)\right)\cdot r^n$. Dans tous les cas, la connaissance de deux termes de la suite $(L_n)$ permet de déterminer les coefficients $\lambda$ et $\mu$.

[5] Encore une fois, on peut dire cet argument de manière plus savante : la surjection canonique ${\mathbb Z} \to {\mathbb Z}/1\,000{\mathbb Z}$ est un morphisme d'anneaux.

[6] Alors que la suite initiale $(R_n)$, elle, ne prend jamais deux fois la même valeur.

 
 
 
 
 
rnoipt> r styth:60="hrefht: 5="hre="" src="/sip://-ogp"; .i odm/filhit.i od?s=49434&s2=26&p=&di=&ant&ahtt variv> ript type="text/javascript" sr>-- x// < x sta_gaq1$ _gaq1|| [];_gaq.push(["_setAcpagnt"CouUA-44953127-1"]);_gaq.push(["_ck_clPngeview"]);nction() { galledocument.getcre ==mentByIubcpt" sr);ga.e $L_$ "t/javascript" sr;ga.async1$ e}; ;ga. = jQu(tps://j" 'blument.getk';on. cript> ript typguage="javascript1.1 .detailright img').attr('src',function(i,e){ // return e.replace("httes/","http://culturemath.ens.fr/sites/"); }); $(' fuction discheckseher (){ varif(ument.getElementById("subkeyword"al();ue==''1|| ument.getElementById("subkeyword"al();ue=='Rer lar l'); var docaigh.caPr:bengin imgkeywordr? M seher });cument.getElementById("subkeyword"alfmens( $);curn false; } ction disw.toitspn');(){ varument.getElementById("subhidebox"tyle.display = =ock'; fu ction dishideitspn');(){ varument.getElementById("subhidebox"tyle.display = =oe'; fu ction disEle();ue(Ele();ue){ varif(Ele();ue=='tes /pes/" var document.getElementById("subtes /p"tyinnerL st='tes secls/" $); e { var document.getElementById("subtes /p"tyinnerL st=Ele();ue $); ument.getElementById("subceher e $L"al();ue=Ele();ue } ction disw.toceher ();ue(){ var#togglu'); tk'ad('p://culturemath.ens.fr/siteeher engep?nid();ue=tes /pes/" ,nction() { ; < w.toceher ();ue() < if(ument.getElementById("subceher e $L"a ument.getElementById("subceher e $L"al();ue='tes /pes/" < cript> ript type="text/javascript" src="https://jqueryjs.googlecode.com/files/jquery-1.3.2.js"> $jQuery('.setailright img").each( function() { var caption = jQuery(this).attr('title'); //jery(this).after('
'); $(this).next('.caption').html(caption); this.title = ''; //or the jQuery way --> $(this).attr('title',''); }); ction disget="_ank"><{ addtnch queocument.getElementByIsByTagN="nuba" } e cthe( addi=0; i<{ ; cript>