Suite de Collatz en engagement direct

dimanche 5 septembre 2010
par  Alain BUSSER

La suite de Collatz est une suite récurrente classique, à ceci près qu’elle fait intervenir des tests dans sa définition dynamique. Ce qui lui donne un intérêt certain du point de vue de l’algorithmique (test et boucle en même temps) d’autant plus que c’est une suite entière. D’ailleurs son succès est tel qu’on la voit dans plusieurs manuels de Seconde (pour éviter de parler de suites en Seconde, on parle de conjecture de Syracuse).

Voici des figures DGPad permettant d’explorer la suite de Collatz en ligne :

  • Suite de Collatz proprement dite (le premier terme est obtenu par la manipulation du curseur u_0) :

En manipulant le curseur ci-dessus, on constate que

    • La fin est toujours la même (4,2,1 à répétition)
    • Mais l’histoire est parfois longue (temps de vol variable), et dans ce cas la suite sort de l’écran
  • La figure ci-dessous affiche le temps de vol sous forme de l’ordonnée d’un point dont l’abscisse est u_0 ; en plus sont affichés les temps de vol des nombres allant de 1 à 200, ce qui explique la longueur de l’ouverture du fichier :
  • Enfin, l’altitude maximum, elle aussi dépendant du terme initial u_0 ; parfois l’altitude maximum est si grande qu’il a fallu la diviser par 100 :

Le TP CaRMetal

L’approche proposée ici a ceci d’original qu’elle demande à l’élève de créer un fichier dynamique, que la suite du TP fera manipuler de manière à émettre le plus spontanément possible les conjectures telles celle de Syracuse. Voici le fichier CaRMetal produit (on peut le télécharger d’un clic droit puis l’ouvrir en local avec CaRMetal) :

la figure dynamique

La conjecture de Syracuse peut s’énoncer ainsi en terme de CaRScript :

Le script suivant :

while(u>1){
    if(Math.floor(u/2)==u/2){
        u/=2;
    } else {
        u=3*u+1;
    }
    Println(u);
}

s’arrête-t-il pour toute valeur initiale entière strictement positive de u ?

Difficile de demander aux élèves de démontrer cette conjecture ! Mais comme on peut le voir ci-dessous (dans le sujet du TP en pdf) il est tout de même possible de placer quelques démonstrations...

Sujet

Le sujet du TP est téléchargeable ci-dessous, sous licence CC :

Creative Commons License
This work is in the Public Domain.

le sujet du TP en pdf

Bonus : Les sources des figures DGPad

  • La suite de Collatz :
// Coordinates System :
SetCoords(68,522,2);


// Geometry :
E2=Expression("E2","","","","x-floor(x/2)*2","12.0","51.6");
u_0=Expression("u_0","","1","60","25","12.0","-22.0");
E1=Expression("E1","","","","(3*x+1)*E2(x)+x/2*(1-E2(x))","12.07","52.9");
E3=Expression("E3","","","","nuage=[[0,u_0]];for(n=1;n<=200;n++){nuage.push([n,E1(nuage[nuage.length-1][1])])};nuage","30.0","50.1");
List1=List("List1",E3);


// Styles :
STL(E2,"c:#224677;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(u_0,"c:#3a2f76;s:4;sn:true;f:16;p:4;i:1;cL:200;cPT:YzojMDAwMGIyO286MTtzOjYuNTtmOjMwO2k6MQ==");
STL(E1,"c:#33157d;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(E3,"c:#295958;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(List1,"c:#760012;o:0.53;s:2;f:30;p:0;sg:0");
SetCoordsStyle("isAxis:true;isGrid:true;isOx:true;isOy:true;isLockOx:false;isLockOy:false;centerZoom:false;color:#111111;fontSize:18;axisWidth:1;gridWidth:0.1");
SetGeneralStyle("background-color:#FAFAFA");
  • L’affichage des temps de vol :
// Coordinates System :
SetCoords(52,282,2);


// Geometry :
E2=Expression("E2","","","","x-floor(x/2)*2","20.0","-68.3");
u_0=Expression("u_0","","1","200","25","20.0","-32.0");
E1=Expression("E1","","","","(3*x+1)*E2(x)+x/2*(1-E2(x))","20.0","-67.0");
E3=Expression("E3","","","","nuage=[[1,4]];for(var u0=2;u0<=200;u0++){var u=u0;n=0;while(u>1){n++;u=E1(u);};nuage.push([u0,n]);};nuage","98.0","30.1");
P1=Point("P1","var u=u_0;var n=0;while(u>1){n++;u=E1(u);};[u_0,n]","0");
List1=List("List1",E3);


// Styles :
STL(E2,"c:#224677;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(u_0,"c:#3a2f76;s:4;sn:true;f:16;p:4;i:1;cL:200;cPT:YzojMDAwMGIyO286MTtzOjYuNTtmOjMwO2k6MQ==");
STL(E1,"c:#33157d;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(E3,"c:#295958;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(P1,"c:#760012;s:10;f:30;p:1;sp:1");
STL(List1,"c:#007c7c;s:1;f:30;p:0;sg:0.6");
SetCoordsStyle("isAxis:true;isGrid:true;isOx:true;isOy:true;isLockOx:false;isLockOy:false;centerZoom:false;color:#111111;fontSize:18;axisWidth:1;gridWidth:0.1");
SetGeneralStyle("background-color:#FAFAFA");
  • Et l’affichage des altitudes maximales divisées par 100 :
// Coordinates System :
SetCoords(55,228,2);


// Geometry :
E2=Expression("E2","","","","x-floor(x/2)*2","18.6","-95.3");
u_0=Expression("u_0","","1","200","25","18.5","-29.0");
E1=Expression("E1","","","","(3*x+1)*E2(x)+x/2*(1-E2(x))","18.5","-94.0");
E3=Expression("E3","","","","nuage=[[1,4]];for(var u0=2;u0<=200;u0++){var max=1;var u=u0;n=0;while(u>1){n++;if(u>max){max=u};u=E1(u);};nuage.push([u0,max/100]);};nuage","96.5","3.1");
P1=Point("P1","var u=u_0;var max=1;var n=0;while(u>1){n++;if(u>max){max=u};u=E1(u);};[u_0,max/100]","0");
List1=List("List1",E3);
E4=Expression("E4","altitude maximum ","","","y(P1)*100","17.5","-61");


// Styles :
STL(E2,"c:#224677;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(u_0,"c:#3a2f76;s:4;sn:true;f:16;p:4;i:1;cL:200;cPT:YzojMDAwMGIyO286MTtzOjYuNTtmOjMwO2k6MQ==");
STL(E1,"c:#33157d;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(E3,"c:#295958;h:1;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO2g6MTtzOjEwO2Y6MzA=");
STL(P1,"c:#760012;s:10;f:30;sp:1");
STL(List1,"c:#007c7c;s:1;f:30;p:0;sg:0.6");
STL(E4,"c:#130515;s:7;f:24;p:4;cL:200;cPT:YzojNzgwMDEzO3M6MTA7ZjozMA==");
SetCoordsStyle("isAxis:true;isGrid:true;isOx:true;isOy:true;isLockOx:false;isLockOy:false;centerZoom:false;color:#111111;fontSize:18;axisWidth:1;gridWidth:0.1");
SetGeneralStyle("background-color:#FAFAFA");

Commentaires