Suite bornée, pas bornée ?

Boécien

Soit $u_{1}=1,\ u_{2}=1$ et $u_{n}=\dfrac{u_{n-1}+u_{n-2}}{\mathrm{pgcd}\left(u_{n-1},u_{n-2}\right)}+(-1)^{n}$ pour $n\geq3$.
Montrer que $u_{n}$ est non bornée.

bisam

Pour ceux qui voudraient jouer, voici un petit script Python qui renvoie la liste des valeurs de la suite $u$ de $1$ à $n$.

from math import gcd
def u(n):
    l = [1,1]
    eps = -1
    for i in range(2,n):
        u1, u2 = l[-2:] # on récupère les deux derniers termes de la liste
        l.append((u1 + u2) // gcd(u1, u2) + eps)
        eps = -eps
    return l

On voit que le comportement est pour le moins étrange.

Par exemple, les termes $u_{6k+4}$ sont égaux à $7$ pour toute valeur $k\in\{1,\dots,19\}$... mais pas au-delà.

jmf

Si seulement il n'y avait pas ce fichu $(-1)^n$ dans la récurrence...
Ou alors on le remplace par $1$, ou par $-1$. Mais pourquoi $(-1)^n$?

marco

$u_n$ est impair quelque soit $n \geq 1$. En effet, si $u_{n-1}$ et $u_{n-2}$ sont impairs, alors leur pgcd $d$ est impair. De plus, $u_{n-1}+u_{n-2}$ est pair, donc $\dfrac{u_{n-1}+u_{n-2}}{d}$ est pair, et $u_n$ est impair.
Or $u_1=u_2=1$ sont impairs. Donc $u_n$ est impair pour tout $n\geq 1$. 

jmf

On est d'accord, mais c'est une indication subliminale.
Si on remplace $(-1)^n$ par $-1$, tous les $u_n$ valent $1$.
Si on remplace $(-1)^n$ par $1$, la suite est ultimement périodique sur les valeurs $3,5,9,15,9,9$.
Si on remplace $(-1)^n$ par $3$, la suite est non bornée.

Si on enlève le terme $(-1)^n$, on obtient la suite de Fibonacci.

jmf

@Boécien ?

jmf

$$\left(\begin{array}{cc}n & u_n\\\hline 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 3 \\ 5 & 3 \\ 6 & 3 \\ 7 & 1 \\ 8 & 5 \\ 9 & 5 \\ 10 & 3 \\ 11 & 7 \\ 12 & 11 \\ 13 & 17 \\ 14 & 29 \\ 15 & 45 \\ 16 & 75 \\ 17 & 7 \\ 18 & 83 \\ 19 & 89 \\ 20 & 173 \\ 21 & 261 \\ 22 & 435 \\ 23 & 7 \\ 24 & 443 \\ 25 & 449 \\ 26 & 893 \\ 27 & 1341 \\ 28 & 2235 \\ 29 & 7 \\ 30 & 2243 \\ 31 & 2249 \\ 32 & 4493 \\ 33 & 6741 \\ 34 & 11235 \\ 35 & 7 \\ 36 & 1607 \\ 37 & 1613 \\ 38 & 3221 \\ 39 & 4833 \\ 40 & 8055 \\ 41 & 7 \\ 42 & 8063 \\ 43 & 8069 \\ 44 & 16133 \\ 45 & 24201 \\ 46 & 40335 \\ 47 & 7 \\ 48 & 40343 \\ 49 & 40349 \\ 50 & 80693 \\ 51 & 121041 \\ 52 & 201735 \\ 53 & 7 \\ 54 & 201743 \\ 55 & 201749 \\ 56 & 403493 \\ 57 & 605241 \\ 58 & 1008735 \\ 59 & 7 \\ 60 & 144107 \\ 61 & 144113 \\ 62 & 288221 \\ 63 & 432333 \\ 64 & 720555 \\ 65 & 7 \\ 66 & 720563 \\ 67 & 720569 \\ 68 & 1441133 \\ 69 & 2161701 \\ 70 & 3602835 \\ 71 & 7 \\ 72 & 3602843 \\ 73 & 3602849 \\ 74 & 7205693 \\ 75 & 10808541 \\ 76 & 18014235 \\ 77 & 7 \\ 78 & 18014243 \\ 79 & 18014249 \\ 80 & 36028493 \\ 81 & 54042741 \\ 82 & 90071235 \\ 83 & 7 \\ 84 & 90071243 \\ 85 & 90071249 \\ 86 & 180142493 \\ 87 & 270213741 \\ 88 & 450356235 \\ 89 & 7 \\ 90 & 64336607 \\ 91 & 64336613 \\ 92 & 128673221 \\ 93 & 193009833 \\ 94 & 321683055 \\ 95 & 7 \\ 96 & 321683063 \\ 97 & 321683069 \\ 98 & 643366133 \\ 99 & 965049201 \\ 100 & 1608415335 \\ 101 & 7 \\ 102 & 1608415343 \\ 103 & 1608415349 \\ 104 & 3216830693 \\ 105 & 4825246041 \\ 106 & 8042076735 \\ 107 & 7 \\ 108 & 1148868107 \\ 109 & 1148868113 \\ 110 & 2297736221 \\ 111 & 3446604333 \\ 112 & 5744340555 \\ 113 & 7 \\ 114 & 5744340563 \\ 115 & 5744340569 \\ 116 & 11488681133 \\ 117 & 17233021701 \\ 118 & 28721702835 \\ 119 & 7 \\ 120 & 4103100407 \\ 121 & 586157201 \\ 122 & 9 \\ 123 & 586157209 \\ 124 & 586157219 \\ 125 & 1172314427 \\ 126 & 1758471647 \\ 127 & 2930786073 \\ 128 & 4689257721 \\ 129 & 2540014597 \\ 130 & 7229272319 \\ 131 & 9769286915 \\ 132 & 16998559235 \\ 133 & 5353569229 \\ 134 & 22352128465 \\ 135 & 27705697693 \\ 136 & 50057826159 \\ 137 & 77763523851 \\ 138 & 42607116671 \\ 139 & 120370640521 \\ 140 & 162977757193 \\ 141 & 283348397713 \\ 142 & 446326154907 \\ 143 & 729674552619 \\ 144 & 392000235843 \\ 145 & 373891596153 \\ 146 & 255297277333 \\ 147 & 629188873485 \\ 148 & 884486150819 \\ 149 & 89039707311 \\ 150 & 973525858131 \\ 151 & 354188521813 \\ 152 & 1327714379945 \\ 153 & 1681902901757 \\ 154 & 3009617281703 \\ 155 & 4691520183459 \\ 156 & 7701137465163 \\ 157 & 4130885882873 \\ 158 & 11832023348037 \\ 159 & 15962909230909 \\ 160 & 27794932578947 \\ 161 & 43757841809855 \\ 162 & 71552774388803 \\ 163 & 115310616198657 \\ 164 & 186863390587461 \\ 165 & 100724668928705 \\ 166 & 287588059516167 \\ 167 & 388312728444871 \\ 168 & 675900787961039 \\ 169 & 1064213516405909 \\ 170 & 1740114304366949 \\ 171 & 2804327820772857 \\ 172 & 4544442125139807 \\ 173 & 816529993990295 \\ 174 & 5360972119130103 \\ 175 & 6177502113120397 \\ 176 & 11538474232250501 \\ 177 & 17715976345370897 \\ 178 & 29254450577621399 \\ 179 & 46970426922992295 \\ 180 & 76224877500613695 \\ 181 & 8213020294907065 \\ 182 & 16887579559104153 \\ 183 & 25100599854011217 \\ 184 & 13996059804371791 \\ 185 & 39096659658383007 \\ 186 & 53092719462754799 \\ 187 & 92189379121137805 \\ 188 & 145282098583892605 \\ 189 & 47494295541006081 \\ 190 & 192776394124898687 \\ 191 & 240270689665904767 \\ 192 & 433047083790803455 \\ 193 & 673317773456708221 \\ 194 & 1106364857247511677 \\ 195 & 1779682630704219897 \\ 196 & 962015829317243859 \\ 197 & 913899486673821251 \\ 198 & 1875915315991065111 \\ 199 & 2789814802664886361 \\ 200 & 4665730118655951473 \\\end{array}\right)$$

i.zitoussi

A cause d'une limite javascript sur le nombre de chiffres significatifs d'un entier, ma suite coïncide avec celle de jmf jusqu'à $u_{175}$ inclus, puis prend une autre route: elle diminue, jusqu'à se stabiliser dans un cycle $(4,4,3,6)$ à partir de $u_{414}$.

Donc je trouve très accidentellement un cycle si on part de $u_1=4$, $u_2=3$ (ou  $u_1=6$, $u_2=4$).

Chaurien

D'où vient cette étrange suite ?

jmf

Je crois qu'elle vient de l'imagination de @Boécien.

jmf

@i.zitoussi

Il semble bien que les cycles (4,4,3,6) (ou encore $(6,4)$, ou $(12,14)$ sous réserve d'en découvrir d'autres) soient des puits dans lequel tombent (in fine) toutes les suites $(u)$ pour peu que l'un au moins de $u_1$ ou $u_2$ soit pair.

jmf

Breaking! J'expérimente avec Mathematica, et le mystère s'épaissit. ça fait vraiment penser à un un ersatz de la suite de Collatz (d'ailleurs ça rime).
Par exemple, avec $u_1=290$ et $u_2=1033$, on trouve, de $u_1$ à $u_{650}$ :

{290, 1033, 1322, 2356, 1838, 2098, 1967, 4066, 6032, 5050, 5540, \

1060, 329, 1390, 1718, 1555, 3272, 4828, 2024, 1714, 1868, 1792, 914, \

1354, 1133, 2488, 3620, 1528, 1286, 1408, 1346, 1378, 1361, 2740, \

4100, 343, 4442, 4786, 4613, 9400, 14012, 5854, 9932, 7894, 8912, \

8404, 4328, 3184, 938, 2062, 1499, 3562, 5060, 4312, 212, 1132, 335, \

1468, 1802, 1636, 1718, 1678, 1697, 3376, 5072, 529, 5600, 6130, \

1172, 3652, 1205, 4858, 6062, 781, 6842, 694, 3767, 4462, 8228, 6346, \

7286, 6817, 14102, 20920, 17510, 3844, 10676, 3631, 14306, 17938, \

16121, 34060, 50180, 325, 776, 1102, 938, 1021, 1958, 2980, 2468, \

1363, 3830, 5194, 4511, 9706, 14216, 11962, 13088, 12526, 12806, \

12667, 25472, 38140, 15902, 27022, 21461, 48484, 69944, 29608, 12443, \

42052, 54494, 48274, 51383, 99658, 151040, 125350, 27638, 76495, \

104132, 180628, 10169, 190798, 200966, 195883, 396848, 592732, \

247394, 60010, 153701, 213712, 367412, 145282, 256346, 200815, \

457160, 131596, 147188, 69697, 216884, 286582, 251732, 269158, \

260444, 264802, 262622, 263713, 526334, 790048, 658190, 724120, \

138230, 86236, 112232, 49618, 80924, 65272, 36548, 25456, 15500, \

10240, 1286, 5764, 3524, 2323, 5846, 8170, 7007, 15178, 22184, 18682, \

20432, 19558, 19994, 19777, 39770, 59548, 49658, 54604, 52130, 53368, \

52748, 26530, 39638, 33085, 72722, 8140, 40430, 4858, 22643, 27502, \

50144, 38824, 11120, 6244, 4340, 379, 4718, 5098, 4907, 10006, 14912, \

12460, 6842, 9652, 8246, 472, 4358, 2416, 3386, 2902, 3143, 6046, \

9188, 7618, 8402, 8011, 16412, 24424, 10208, 4330, 7268, 5800, 3266, \

4534, 3899, 8434, 12332, 10384, 5678, 8032, 6854, 7444, 7148, 3649, \

10796, 14446, 12620, 13534, 13076, 13306, 13190, 13249, 26438, 39688, \

33062, 36376, 34718, 35548, 35132, 17671, 52802, 70474, 61637, \

132112, 193748, 81466, 137606, 15649, 153254, 168904, 161078, 3838, \

82457, 86296, 168752, 31882, 100316, 66100, 41603, 107704, 149306, \

128506, 138905, 267412, 406316, 168433, 574748, 743182, 658964, \

701074, 680018, 690547, 1370564, 158548, 29405, 187954, 217358, \

202657, 420014, 88954, 254483, 343438, 597920, 470680, 26714, 248698, \

137705, 386404, 524108, 227629, 751736, 979366, 865550, 922459, \

1788008, 2710468, 1124618, 1917544, 1521080, 429829, 1950908, \

2380738, 2165822, 2273281, 4439102, 6712384, 5575742, 6144064, \

5859902, 6001984, 5930942, 5966464, 5948702, 5957584, 5953142, \

5955364, 58952, 1503580, 390632, 473554, 432092, 452824, 221228, \

168514, 194870, 181693, 376562, 558256, 467408, 64105, 531512, \

595618, 563564, 579592, 285788, 216346, 251066, 233707, 484772, \

718480, 300812, 254824, 138908, 98434, 16952, 57694, 2870, 4327, \

7196, 11524, 4679, 16204, 20882, 18544, 19712, 2392, 2762, 2578, \

2669, 5248, 7916, 3292, 2801, 6094, 8894, 7495, 16388, 23884, 10067, \

33952, 44018, 38986, 41501, 80488, 121988, 50620, 43151, 93772, \

136922, 115348, 126134, 120742, 123437, 244180, 367616, 152950, \

260282, 206617, 466898, 673516, 570206, 621862, 596033, 1217896, \

1813928, 378979, 2192906, 2571886, 2382395, 4954282, 7336676, \

6145480, 3370538, 4758010, 4064273, 8822284, 12886556, 5427211, \

18313766, 23740978, 21027371, 44768350, 65795720, 11056408, 9606515, \

20662924, 30269438, 25466182, 27867809, 53333992, 81201800, 16816975, \

3920750, 829510, 475025, 260908, 735932, 249211, 985142, 1234354, \

1109747, 2344102, 3453848, 2898976, 794102, 1846540, 1320320, 158344, \

184832, 42898, 113864, 78382, 96122, 87253, 183374, 270628, 227000, \

124408, 43925, 168334, 212258, 190297, 402554, 592852, 497702, \

545278, 521489, 1066768, 26036, 273202, 149618, 211411, 361028, \

572440, 233366, 402904, 318134, 360520, 339326, 349924, 344624, \

173638, 15242, 94441, 109682, 204124, 156902, 180514, 168707, 349222, \

517928, 433576, 118937, 42502, 161438, 101971, 263408, 365380, \

157196, 130645, 287840, 83698, 185768, 134734, 160250, 147493, \

307742, 455236, 381488, 209182, 295334, 252259, 547592, 799852, \

336860, 284179, 621038, 905218, 763127, 1668346, 2431472, 2049910, \

2240690, 429061, 2669750, 3098812, 2884280, 1495774, 312860, 904318, \

608588, 756454, 682520, 719488, 175250, 447370, 62261, 509632, \

571892, 270382, 421136, 345760, 47930, 39370, 8729, 48100, 56828, \

26233, 83060, 109294, 96176, 102736, 12431, 115168, 127598, 121384, \

124490, 122938, 123713, 246652, 370364, 154255, 524618, 678874, \

601745, 1280620, 376472, 414274, 395372, 404824, 200048, 75610, \

137828, 106720, 61136, 10492, 17906, 14200, 16052, 7564, 5903, 13468, \

19370, 1264, 10316, 2896, 3302, 3100, 3200, 64, 50, 58, 53, 112, 164, \

70, 116, 94, 104, 100, 50, 4, 26, 16, 20, 10, 2, 7, 8, 16, 2, 10, 5, \

4, 8, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, \

2, 4}

jmf

Et voilà la trajectoire des $(n,u_n)$ dans l'exemple ci-dessus. Je renonce à comprendre.

jmf

Et en choisissant $u_1$ et $u_2$ tous les deux impairs, on n'est pas à l'abri de surprises. Exemple $u_1=7$ et $u_2=9$, où on tombe dans le cycle $(7,17,23,41,63,105)$. 

zeitnot

Pour jmf :

jmf

@zeitnot

Merci pour la rime :-)

Boécien

Merci pour vos contributions. Je n'ai pas la réponse à ma question qui m'est venue en m'amusant avec des variations autour de Fibonacci. Pour le cas $u_1=u_2=1$ je conjecture que $\lim_{n\rightarrow\infty}u_{n}^{1/n}=1.22...>1$ existe. Amusant l'exemple de jmf qui finit sur le cycle de Collatz.

jmf

Tu aurais pu le dire, que tu n'avais pas la réponse à ta question...

Boécien

Désolé de n'avoir pas été assez explicite sur le fait que c'était une question ouverte. C'était un peu dans le titre.

En fixant $u_1=1$  alors il semble que si $u_2$ est impair  la suite rejoint le cycle $(4,4,3,6)$ et si $u_2$ est impair $u_n$ diverge avec $\lim_{n\rightarrow\infty}u_{n}^{1/n}=C$ où $C=1.22...$.

EDIT: coquille corrigée après la remarque de jmf

SaladeDeFoudre

Avec ${\mathrm{pgcd}\left(u_{n-1},u_{n-2}\right)} = u_{n-1}+u_{n-2} - u_{n-1}u_{n-2} + 2\sum\limits_{k=0}^{u_{n-2}-1}E\big(k(u_{n-1}/u_{n-2})\big)$.

Je trouve que si $u_{n}$ tend vers $+\infty$, alors $u_{n-1}u_{n-2} -2\sum\limits_{k=0}^{u_{n-2}-1}E\big(k(u_{n-1}/u_{n-2})\big)$ est équivalent à $u_{n-1}+u_{n-2}$, je ne sais pas si ça avance plus que ça.

jmf

Boécien a dit :

En fixant $u_1=1$  alors il semble que si $u_2$ est impair  la suite rejoint le cycle $(4,4,3,6)$

Si $u_2$ est pair, tu veux dire.
Quant à la limite des $u_n^{1/n}$, je pense que c'est une spéculation un peu risquée.
Voici le tracé des $u_n^{1/n}$, avec $1000\le n\le 50000$

Math Coss

Attention avec les rimes : « Batz » se prononce » [bɑ] alors qu'ersatz (et sans doute Collatz) se prononce(nt) [ats].

La suite ? Aucune idée.

Boécien

@etanche  @jmf

J'ai poussé plus loin le calcul de ${u_n}^{1/n}$ (jusqu'à $620000$) voici le tracé de $(n,{u_n}^{1/n})$ tous les $10000$. Je maintiens ma conjecture sur l'existence d'une limite commune $C=1.22...$ lorsque $u_1=1$ et $u_2$ est impair.

EDIT1: calcul poussé jusqu'à 720000

EDIT2: calcul poussé jusqu'à 880000

EDIT3: calcul poussé jusqu'à 10^6

EDIT4: calcul poussé jusqu'à 1 240 000

EDIT5: calcul poussé jusqu'à 1 470 000

EDIT6: calcul poussé jusqu'à 2 110 000

EDIT7: calcul poussé jusqu'à 2 550 000

etanche

@Boêcien avec quel logiciel as-tu poussé ton calcul ? Merci.

Boécien

@etanche avec pari gp.  Je suis en train d'atteindre 10^6 et la convergence vers C se maintient.

@etanche et voici le code que j'utilise pour recueillir les valeurs tous les 10000 n

u1=1;u2=1;for(n=3,10^6,u3=(u2+u1)/gcd(u2,u1)+(-1)^n;u1=u2;u2=u3;if(n%10000==0,print(n,"    ",u3^(1/n),"")))

Boécien

Si on suppose que la probabilité que $pgcd\left(u_{n-1},u_{n-2}\right)=2m+1$ pour $m=0,1,2,...$ vaut  $\frac{3}{4\left(2m+1\right)^{2}}\frac{1}{\zeta(2)}$ on peut estimer que la suite $u_{n}$ se comporte comme la suite $v_{n}$ définie par $v_{n}=\lambda_{n}\left(v_{n-1}+v_{n-2}\right)$ où $\lambda_{n}$ est un coefficient aléatoire prenant ses valeurs dans $\{\frac{1}{2m+1}\} _{m\in\mathbb{N}}$ avec probabilité $\frac{3}{4\left(2m+1\right)^{2}}\frac{1}{\zeta(2)}$ .

Or ici il semble que la probabilité que par exemple $pgcd\left(u_{n-1},u_{n-2}\right)=1$ n'est pas $\frac{3}{4\zeta(2)}=0.8...$ mais plus proche de $0.7$. Quelqu'un a une idée de meilleure heuristique pour la probabilité que $pgcd\left(u_{n-1},u_{n-2}\right)=2m+1$ ?

Boécien

Au fait je suis originaire de Roscoff, merci Zeitnot.

marco

@jmf : bonjour, comment fais-tu pour montrer que la suite n'est pas bornée si on remplace $(-1)^n$ par $3$ ?

jmf

Bonjour,

j'aurais dû dire "si on remplace $(-1)^n$ par $3$, la suite $(u)$ semble non bornée".
Tout ça est très curieux... Le tableau ci-dessous donne les lignes $\{n,\text{pgcd}(u_{n-1},u_{n-2})\}$ quand ce pgcd est strictement supérieur à $1$ (la suite étant initialisée par $u_1=u_2=1$)
Par exemple, pour la dernière ligne, on a $u_{1537}=\dfrac{u_{1536}+u_{1535}}{7}+3$.
Le plus étonnant est que la situation $\text{pgcd}(u_{n-1},u_{n-2})>1$ ne semble plus se produire après.... Si cela s'avérait vrai (mais je spécule), on pourrait écrire les $u_n$ (au bout d'un certain temps) comme une combinaison de suites de Fibonacci/Lucas.

$\begin{pmatrix} 11 & 7 \\ 14 & 7 \\ 25 & 5 \\ 30 & 13 \\ 38 & 11 \\ 39 & 11 \\ 42 & 7 \\ 43 & 5 \\ 63 & 25 \\ 125 & 349 \\ 129 & 49 \\ 130 & 7 \\ 135 & 5 \\ 136 & 5 \\ 137 & 5 \\ 138 & 5 \\ 139 & 5 \\ 142 & 11 \\ 143 & 7 \\ 156 & 5 \\ 158 & 7 \\ 159 & 49 \\ 162 & 7 \\ 226 & 43 \\ 234 & 5 \\ 242 & 7 \\ 243 & 7 \\ 246 & 49 \\ 261 & 5 \\ 281 & 5 \\ 282 & 5 \\ 918 & 1153 \\ 926 & 17 \\ 930 & 61 \\ 932 & 5 \\ 952 & 5 \\ 953 & 11 \\ 955 & 5 \\ 959 & 11 \\ 979 & 17 \\ 980 & 11 \\ 982 & 25 \\ 985 & 5 \\ 986 & 5 \\ 987 & 5 \\ 989 & 7 \\ 1001 & 7 \\ 1017 & 7 \\ 1029 & 7 \\ 1501 & 257 \\ 1505 & 7 \\ 1521 & 7 \\ 1537 & 7 \end{pmatrix}$

marco

D'accord, merci. J'avais tenté de montrer que $\mathrm{pgcd}(u_{n-1},u_{n-2})=1$, on aurait alors $u_n=u_{n-1}+u_{n-2}+3$. Donc $u_n=4F_n-3$ où $(F_n)$ est la suite de Fibonacci avec $F_1=F_2=1$. Donc il suffirait de montrer que $\mathrm{pgcd}(4F_{n-1}-3, 4F_{n-2}-3)=1$ pour tout $n>2$ pour montrer que $\mathrm{pgcd}(u_{n-1},u_{n-2})=1$ et $u_n=4F_n-3$ pour tout $n>2$, et donc $(u_n)$ non bornée.

Boécien

Je n'observe pas la même chose que jmf pour le cas $u_1=u_2=1$. Soit

$$R(n)=\left|\left\{ 2\leq k\leq n,\:pgcd\left(u_{k},u_{k-1}\right)=1\right\} \right|$$

 alors il semble que $\frac{R(n)}{n}\rightarrow0.7...$ et pas $1$. Je lance un calcul de $(n,R(n))$ pour tracer $\frac{R(n)}{n}$. Image actualiée ci-dessous.

EDIT1: R(n)/n tous les 10000 jusqu'à 460 000

EDIT2: R(n)/n tous les 10000 jusqu'à 1 210 000

EDIT3: R(n)/n tous les 10000 jusqu'à 1 640 000