Le temps passant, je peux bien le dire : la fonction-mystère permet le passage du numéro d'ordre d'une fraction dans le système Calkin-Wilf au numéro de la même fraction, mais dans Stern-Brocot. J'avais trouvé qu'en inversant les bits de la représentation binaire du numéro (sauf le premier, toujours à 1), on arrivait à ce résultat. La fonction exécutée deux fois redonne le numéro de départ. Quand les bits concernés forment un palindrome, le nombre est inchangé. Je ne sais pas quel propriété particulière pourrait avoir ces fractions ayant le même rang dans Calkin-Wilf et dans Stern-Brocot.
L'introduction du MPO 98 m'a donné une petite idée d'éclairage supplémentaire des rationnels : pourquoi pas sous la forme c + a/b, avec a<b. Lors de chaque affichage de a/b dans un programme, je pourrais toujours faire la division euclidienne pour déterminer le nouveau a et c. J'ai préféré rechercher une méthode incrémentale de calcul de ces trois entiers à chaque étape du parcours en profondeur de l'arbre binaire.
Départ : a=0 ; b=1 ; c=1
Descente vers fils gauche : A=b*c+a : B=A+b : C=0
Descente vers fils droit : C=c+1
Remontée dans l'arbre :
si c=0 ; [fils gauche] B=b-a ; C=int(a/B) ; A=a-C*B
si c>0 ; [fils droit] C=c-1
Comme pour a/b et le numéro de rationnel, cette représentation a son propre test de détermination de l'origine (gauche ou droite) à la remontée. Les lettres majuscules indiquent qu'il s'agit de valeurs calculées à cette étape, ce qui permet d'ordonner les affectations dans le code.
Voici ce à quoi ressemblent les 127 premiers rationnels dans un arbre en H "droit" (valeurs extrêmes dans les coins) :
Code : Tout sélectionner
0+1/7 0+6/11 0+4/15 0+11/18 0+2/11 0+9/16 0+5/18 0+13/21
0+1/6 0+1/5 1+1/5 0+4/11 0+4/7 1+4/7 0+2/9 0+2/7 1+2/7 0+5/13 0+5/8 1+5/8
1+1/6 | 2+1/5 1+4/11 | 2+4/7 1+2/9 | 2+2/7 1+5/13 | 2+5/8
0+1/4 ______ 0+1/3 ______ 1+1/3 0+2/5 ______ 0+2/3 ______ 1+2/3
0+5/14 | 0+9/13 | 0+7/17 | 0+10/13 0+7/19 | 0+12/17 | 0+8/19 | 0+11/14
0+5/9 1+1/4 2+1/4 | 0+7/10 2+1/3 3+1/3 0+7/12 1+2/5 2+2/5 | 0+8/11 2+2/3 3+2/3
1+5/9 3+1/4 | 1/7/10 4+1/3 1+7/12 3+2/5 | 1+8/11 4+2/3
0+1/2 ___________________ 1+0/1 ____________________ 2+0/1
0+3/14 0+11/19 | 0+5/17 0+12/19 0+3/13 0+10/17 | 0+4/13 0+9/14
0+3/11 0+3/8 1+3/8 | 0+5/12 0+5/7 1+5/7 0+3/10 0+3/7 1+3/7 | 0+4/9 0+4/5 1+4/5
1+3/11 | 2+3/8 | 1+5/12 | 2+5/7 1+3/10 | 2+3/7 | 1+4/9 | 2+4/5
0+3/5 ______ 1+1/2 ______ 2+1/2 0+3/4 ______ 3+0/1 ______ 4+0/1
0+8/21 | 0+13/18 0+7/16 | 0+9/11 0+7/18 | 0+11/15 0+5/11 | 0+6/7
0+8/12 1+3/5 2+3/5 0+7/9 3+1/2 4+1/2 0+7/11 1+3/4 2+3/4 0+5/6 5+0/1 6+0/1
1+8/13 3+3/5 1+7/9 5+1/2 1+7/11 3+3/4 1+5/6 7+0/1
J'ai laissé toutes les valeurs de a, b et c. On peut faire d'autres choix d'affichage.
Programmeur abscons.