boucles

kolotoko · February 2017

Bonjour,

considérons le nombre 2017 et le triplet de nombres (2017, 1, 1).

A un triplet d'entiers relatifs (x, y, z) on fait correspondre le triplet (x - y - z , y , 2y + z ) si y + z < x ;
ou on lui fait correspondre le triplet (y + z - x , x , 2x - z) si y + z > x .

Partant de (2017, 1, 1) et en réitérant le processus, on finit par revenir au point de départ .

Combien de triplets différents contient la boucle qui part de (2017, 1, 1 ) et revient à (2017, 1, 1) ?

Bien cordialement.

kolotoko

fredrick · February 2017

96

kolotoko · February 2017

Bonsoir,

97, non ?

Bien cordialement.

kolotoko

fredrick · February 2017

Non le 97° correspond au premier triplet, donc il n'entre pas dans le cadre de ta question qui demande le nombre de triplet "différents".

fredrick · February 2017

C'est amusant ta boucle, quand la valeur de $x$ de départ est le produit de 2 nombres premiers jumeaux et $y=1$ et $z=2$, $x$ prend la valeur 0 entre ces 2 nombres premier, exemple pour 17*19=323, $x=0$ au 18° tour de boucle :

1 : x= 323  ; y= 1  ; z= 2
2 : x= 320  ; y= 1  ; z= 4
3 : x= 315  ; y= 1  ; z= 6
4 : x= 308  ; y= 1  ; z= 8
5 : x= 299  ; y= 1  ; z= 10
6 : x= 288  ; y= 1  ; z= 12
7 : x= 275  ; y= 1  ; z= 14
8 : x= 260  ; y= 1  ; z= 16
9 : x= 243  ; y= 1  ; z= 18
10 : x= 224  ; y= 1  ; z= 20
11 : x= 203  ; y= 1  ; z= 22
12 : x= 180  ; y= 1  ; z= 24
13 : x= 155  ; y= 1  ; z= 26
14 : x= 128  ; y= 1  ; z= 28
15 : x= 99  ; y= 1  ; z= 30
16 : x= 68  ; y= 1  ; z= 32
17 : x= 35  ; y= 1  ; z= 34
[color=#FF0000]18 : x= 0  ; y= 35  ; z= 36[/color]
19 : x= 71  ; y= 0  ; z= -36
20 : x= 107  ; y= 0  ; z= -36
21 : x= 143  ; y= 0  ; z= -36
22 : x= 179  ; y= 0  ; z= -36
23 : x= 215  ; y= 0  ; z= -36
24 : x= 251  ; y= 0  ; z= -36
25 : x= 287  ; y= 0  ; z= -36

Et $z= 17+19$

Autre exemple avec 71*72=5183 (je ne mets pas toute la liste) :

68 : x= 560  ; y= 1  ; z= 136
69 : x= 423  ; y= 1  ; z= 138
70 : x= 284  ; y= 1  ; z= 140
71 : x= 143  ; y= 1  ; z= 142
[color=#FF0000]72 : x= 0  ; y= 143  ; z= 144[/color]
73 : x= 287  ; y= 0  ; z= -144
74 : x= 431  ; y= 0  ; z= -144
75 : x= 575  ; y= 0  ; z= -144

kolotoko · February 2017

Bonjour ,

on s'est mal compris :

je n'ai pas écrit combien de triplets différents du premier triplet (96) contient la boucle, mais combien de triplet différents contient la boucle (97) .

Imaginons un autre exemple :

(7, 1, 1) donne (5, 1, 3) donne (1, 1, 5) donne (5, 1, -3) donne (7, 1, -1) donne (7, 1, 1, ) donne (5, 1, 3) donne ((1, 1, 5) etc.

Ici la boucle contient 5 triplets différents.

A remarquer que la longueur de la boucle (notée f(n) ) quand on part du triplet (n, 1, 1) semble bien imprévisible :

Par exemple :

f(2017) = 97, f(2018) = 142, f(2019) = 103, f(2020) = 383, f(2021) = 98, f(2022) = 773 etc (en espérant ne pas m'être trompé) .

Bien cordialement.

kolotoko

bisam · February 2017

Alors, on définit le matériel :

def f(triplet):
    x, y, z = triplet
    return (x-y-z, y, 2*y+z) if y+z < x else (y+z-x, x, 2*x-z)

def longueur_boucle(origine):
    n = 1
    triplet = f(origine)
    while triplet != origine:
        triplet = f(triplet)
        n += 1
    return n

Puis on demande gentiment :

[longueur_boucle((i,1,1)) for i in range(2017,2037)]

et pouf, on obtient :

[97, 142, 103, 383, 98, 773, 137, 122, 91, 110, 102, 132, 135, 176, 129, 490, 158, 526, 204, 94]

ev · February 2017

Waouh ! C'est super !

Est-ce qu'il y a un kolotokopyright ?

e.v.

fredrick · February 2017

Très beau programme, je savais pas qu'on pouvait appeler les variables de cette façon dans une fonction en Python, très pratique.
Cela dit si je ne me trompe pas, ce programme donne le nombre de tour pour revenir à l'origine, mais pas le nombre de triplets différents.

kolotoko · February 2017

Bonjour,

si on part de certains triplets , la longueur de boucle est parfois très longue : par exemple, en partant de (756, 756, 653) on trouve 20683 .

Très mystérieux, tout ça .

Bien cordialement.

kolotoko

depasse · February 2017

Si on part de (2,1,1), c'est quoi la suite? :-D

bisam · February 2017

fredrick a écrit:

Cela dit si je ne me trompe pas, ce programme donne le nombre de tour pour revenir à l'origine, mais pas le nombre de triplets différents.

Tu as raison, mais comme c'est une suite récurrente à un seul prédécesseur, si on retombe sur un triplet déjà présent, on tombe dans une boucle... et on ne revient jamais à l'origine.
Du coup, si on revient à l'origine, c'est que tous les éléments de la boucle sont distincts.

Shah d'Ock · February 2017

Si ce n'est indiscret, ça vient d'où cette suite de triplet?

Stator · February 2017

Je pense voir pourquoi il y a des boucles. En partant de (x(0),y(0),z(0)) soit (x(n),y(n),z(n)) le triplet obtenu après n étapes. Alors on peut montrer que x(n),y(n),z(n) sont des suites bornées. Comme ce sont des entiers (x(n),y(n),z(n)) prend ses valeurs dans un ensemble fini de triplets et forcément il y a un cycle.

Shah d'Ock · February 2017

Stator, tu as regardé l'exemple proposé dans le mot de Depasse?

Stator · February 2017

Ce n'est pas un bon exemple puisqu'on n'a pas 2<2 ni 2>2 et l'algo est indéterminé dès la première itération (avec la définition originale de kolotoko).

Shah d'Ock · February 2017

C'est vrai j'avais automatiquement remplacé dans ma tête le second cas par "sinon". Autant pour moi.

depasse · February 2017

Bonjour à tous,

Stator,
Si mon exemple $(2,1,1)$ n'est pas bon, alors
1)l'algorithme de bisam n'est pas bon,
2) l'exemple $(6,1,1)$ n'est pas bon.

Déterminer les $(x,y,z)$ de $N^3$ sur lesquels est définie toute itérée de la fonction définie par kolotoko sur $N^3$ privé des $(x,y,z)$ tels que $x=y+z$ me semble très difficile.
Supposons pourtant qu'on y parvienne et qu'on parvienne de plus à prouver que toute suite finit par boucler; il faudra encore montrer qu'elle boucle sur son premier terme et les seuls arguments de bornitude me semblent insuffisants.

Sauf etc...

Pratiquement, il me semble sage de considérer que kolotoko a fait un typo en oubliant le cas $x=y+z$ mais il faut attendre son avis!
Même ainsi simplifié, ça doit pas être de la tarte d'étudier la fonction "longueur du cycle"!

Cordialement
Paul

Edit

depasse · February 2017

Bonsoir,

je me renie partiellement:

Si on prouve que le programme de bisam (basé sur $y+z<x$ ou $y+z$ $\geq$$x$) termine pour toute entrée, alors il termine en particulier pour toute entrée $(x,y,z)$ pour laquelle on ne passe jamais par le cas $y_n+z_n=x_n$. Bref il n'y a pas à se casser la tête pour trouver les "mauvais exemples". L'exemple $(7,1,1)$ de kolotoko est rassurant: il prouve qu'il n'y a pas que des mauvais exemples!

Breyer · February 2017

L'idée de Stator est bonne moyennant quelques précautions suggérées par depasse. Ensuite on peut construire l'algorithme à l'envers i.e on peut exprimer $x(n),y(n),z(n)$ en fonction de $x(n+1),y(n+1),z(n+1)$. Ainsi s'il boucle il revient sur le point de départ.