Problème 2/3
Soit à définir l’application F dans IN telle que Un+1 = F(Un)
La forme explicite de F se décompose en :
F0(x) = x/3 |
pour x = 0 mod 3 |
ou bien en posant x = 3n (n entier naturel) : |
3 n + 0 -----> n |
F1(x) = (2 x +1) / 3 |
pour x = 1 mod 3 |
ou bien en posant x = 3n + 1 : |
3 n + 1 -----> 2 n + 1 |
F2(x) = (2 x + 2) / 3 |
pour x = 2 mod 3 |
ou bien en posant x = 3 n + 2 : |
3 n + 2 -----> 2 n + 2 |
Les suites ainsi définies approchent dans IN les suites dans IR définies par Un+1 = 2/3 Un
Illustration graphique :
Les lignes bleues illustrent la convergence vers 2 et les lignes vertes la convergence vers 1.
Il ressort de la définition que 0 est un point fixe isolé que 1 et 2 sont des points doubles et qu’à partir de 1 ou 2 la suite devient stationnaire. Pour Un >2 la suite est strictement décroissante.
Ainsi pour U0 > 0 la suite Un converge soit vers 1 soit vers 2.
Ne pas confondre avec la suite explicite Un = 1.5 x 0.5 x (-1)n qui admet 1 et 2 comme valeurs d’adhérence.
L’arbre des suites possibles comporte 2 composantes connexes distinctes les antécédents de 1 et ceux de 2
Chaque entier supérieur à 2 a exactement 2 antécédents dont 1 par F0
L’arbre des antécédents présente des régularités :
1 |
2 |
||||||||||||||||||||||||||||||
3 |
6 |
||||||||||||||||||||||||||||||
9 |
4 |
18 |
8 |
||||||||||||||||||||||||||||
27 |
13 |
12 |
5 |
54 |
26 |
24 |
11 |
||||||||||||||||||||||||
81 |
40 |
39 |
19 |
36 |
17 |
15 |
7 |
162 |
80 |
78 |
38 |
72 |
35 |
33 |
16 |
||||||||||||||||
243 |
121 |
120 |
59 |
117 |
58 |
57 |
28 |
108 |
53 |
51 |
25 |
45 |
22 |
21 |
10 |
486 |
242 |
240 |
119 |
234 |
116 |
114 |
56 |
216 |
107 |
105 |
52 |
99 |
49 |
48 |
23 |
Les impairs sont en gras, les 3n en vert les 3n+1 en bleu et les 3n+2 en marron
Remarquons sur la dernière ligne que les termes sur fond bleu ou marron approchent la moitié du terme en vert qui les précède
La lecture du tableau dans le sens de la succession des termes de la suite s’effectue de bas en haut en restant dans la même colonne . Exemple : 28 – 19 – 13 – 9 – 3 – 1
Quelques régularités du tableau :
2 n + 1 |
← 3 n + 1 |
2 n + 2 |
← 3 n + 2 |
6 n + 3 |
← 9 n + 4 |
6 n + 6 |
← 9 n + 8 |
18 n + 9 |
← 27 n + 13 |
|
|
3k ( 2 n + 1) |
← 3k + 1 n + 3 (3k -1)/2 +1 |
3k (2 n +2 ) |
← 3k+1 n + 3 (3k – 1) + 2 |
3k+1( 2 n + 1) |
← 3k + 2 n + 3 (3k+1 -1)/2 +1 |
|
|
3k s’écrit en base 3 un « 1 » suivi de k « 0 » . Ainsi 3k - 1 s’écrit avec une succession de k « 2 » et le nombre obtenu est pair. La division par 2 conduit à une succession de k « 1 ».
La base 3 étant impaire le nombre écrit avec une succession de k « 1 » a la parité de k.
Les 2 derniers termes constants de la colonne bleue sont donc de parité différentes comme le sont plus haut 1, 4 et 13
Dans la colonne marron les termes constants sont tous pairs
En conséquence dans la partie gauche les termes en dessous à droite des termes bleus ( 4, 13 40 ) sont alternativement marron et bleus (5, 19 ,59)
Dans la partie droite , en dessous à droite des termes marron (8, 26, 80 ) les termes sont tous marron : (11, 38 119)
Itérations de F de manière à accélérer la convergence.
Dans la formule 3 n --> n on peut éclater n en : 3 n ; 3 n + 1 et 3 n + 2
Soit 3 x 3 n --> 3 n ---> n
3x( 3 n +1) --> (3 n + 1) --> 2 n + 1
3x( 3 n + 2) --> (3 n + 2)---> 2 n + 2
On peut procéder de même dans les autre formules et obtenir pour F2 :
9 n |
→ |
n + 0 |
9 n + 3 |
→ |
2 n + 1 |
9 n + 6 |
→ |
2 n + 2 |
9 n + 1 |
→ |
4 n + 1 |
9 n + 4 |
→ |
2 n + 1 |
9 n + 7 |
→ |
4 n + 4 |
9 n + 2 |
→ |
4 n + 2 |
9 n + 5 |
→ |
4 n +3 |
9 n + 8 |
→ |
2 n + 2 |
On pourrait ainsi définir Fk qui comporte 3k lignes
Le calcul des termes intermédiaires est remplacé par les calculs nécessaires à la recherche de la bonne ligne !