On définit une suite {(a_n)_{n\ge0}} par {a_0=1} et : {\forall\,n\in\mathbb{N},\;\begin{cases}a_{2n+1}=a_n\cr a_{2n+2}=a_{n}+a_{n+1}\end{cases}}
Question 1.
Soient {r} et {s} deux entiers premiers entre eux.
Montrer qu’il existe {n} tel que {\begin{cases}a_n=r\\a_{n+1}=s\end{cases}}
Indication : récurrence forte sur la valeur de {r+s}.
|
Cliquer ici pour voir (ou cacher) la réponse
Si {r+s=2}, donc si {r=s=1}, c’est évident car {a_0=1} et {a_1=1}.
On se donne {r,s} premiers entre eux, avec {r+s>2} (ils sont donc distincts).
On suppose la propriété vraie pour les entiers {r',s'} premiers entre eux tels que {r'+s'\lt r+s}.
-
Si {r>s}, alors par hypothèse de récurrence, il existe {m} tel que {a_m=r-s} et {a_{m+1}=s} (car {r-s} et {s} sont premiers entre eux).
On a alors {a_{2m+2}=r} et {a_{2m+3}=s}.
-
Si {r\lt s}, alors par hypothèse de récurrence, il existe {m} tel que {a_m=r} et {a_{m+1}=s-r}.
On a alors {a_{2m+1}=r} et {a_{2m+2}=s}.
Dans tous les cas, on a trouvé {n} dans {\mathbb{N}} tel que {a_n=r} et {a_{n+1}=s}, ce qui achève la récurrence.
Question 2.
Écrire une fonction Python «a», prenant en argument un entier {n\ge0}, et renvoyant {a_{n}}.
La fonction «a» utilisera bien sûr la définition récursive de la suite {(a_{n})_{n\ge0}}.
Pour mémoriser les appels récursifs, on utilisera un dictionnaire {A} formé d’enregistrements {k :a_{k}}, initialisé par {A=\{0 :1\}} c’est-à-dire {a_{0}=1}.
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Question 3.
Écrire quelques lignes de Python pour afficher les 100 premières valeurs de la suite {a} dans un tableau {10\times 10} (on recommande l’extension Numpy).
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :
Question 4.
Écrire une fonction Python nommée «gcd», et calculant le pgcd de deux entiers.
Écrire une fonction Python nommée «find», prenant en arguments deux entiers naturels {r} et {s}, et renvoyant un entier {n} tel que {a_{n}=r} et {a_{n+1}=s}.
|
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez :
Pour poursuivre votre exploration, vous pouvez :