La suite définie récursivement par et avec permet effectivement de répertorier tous les rationnels.
Les 32 premiers rationnels répertoriés par cette suite sont les suivants :
Code : Tout sélectionner
U(n) = a_n / b_n
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
a_n 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1...
U-n= ─── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ──
b_n 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6...
En effet cette suite parcourt en largeur l'arbre de Calkin-Wilf qui est en bijection avec l'ensemble (infini) des rationnels strictement positifs. Cet arbre ressemble à l'arbre de Stern-Brocot qui lui aussi permet de répertorier tous les rationnels mais d'une autre façon. Les deux arbres se ressemblent énormément, seul l'ordre des rationnels au sein de chaque niveau change. Mais ce sont les mêmes éléments.
(j'aime bien cette façon de faire pour dessiner l'arbre, mais à chaque nœud, j'aurais tourné dans l'autre sens en mettant le rationnel le plus petit à gauche et le plus grand vers la droite. C'est un détail.
Il manque deux niveaux, on ne voit sur cette figure que le grand-père de U(500) c'est à dire U(125) ! Vous l'avez trouvé ?)
Ce qui est pratique et explique la plupart des propriétés curieuses de cette séquence est que l'arbre de Calkin-Wilf (comme celui plus ancien de Stern-Brocot) est un arbre binaire. C'est à dire qu'à chaque rationnel est associé exactement deux autres rationnels fils, l'un plus petit et l'autre plus grand.
C'est une idée simple et géniale ; pour tout élément de l'arbre,
le fils situé à gauche (celui de valeur plus faible que U(n)) sera ,
le fils situé à droite (celui de valeur plus fort que U(n) ) sera
En le construisant de cette façon, l'arbre contiennent tous les rationnels positifs irréductibles. Comme il s'agit d'un arbre binaire, les indices de la suite le parcourant en largeur (pas trop le choix en fait ; difficile de parcourir en profondeur un arbre de dimension infinie !) donne la position dans l'arbre.
On peut donc construire l'arbre de proche en proche, ce qui revient à la méthode brute qui consiste à calculer tous les U(n) jusqu'à arriver à U(500).
la définition des fils par a rapport au dénominateur et numérateur de leur père fait que cette suite U(n) se construit à partir d'une séquence particulière Fusc(n) (Suite de Sterne), la même en fait que celle de l'autre arbre. C'est la façon dont on a défini les deux fils de chaque rationnel de l'arbre qui explique pourquoi le dénominateur du premier est le numérateur du suivant. Et comme l'autre partie de la fraction s'obtient par l'addition de termes consécutifs, cette séquence contient du Fibonacci et du triangle de Pascal, ce qui explique sa curieuse définition récurrente.
Mais l'on peut aussi déduire de la décomposition binaire de n quelle est sa position dans l'arbre. A partir de ce point deux stratégies peuvent être utilisées pour déterminer U(n),
* soit on refait le calcul jusqu'à revenir à la racine, par exemple à l'aide de combinaison de matrices (cf. code post précèdant),
* soit on utilise un propriété des fractions continues.
Tous les rationnels ont un développement en fraction continue fini (contrairement aux nombres réels, nombres transcendantaux et irrationnels).
Et justement, l'arbre de Calkin-Wilf (comme en partie l'arbre de Sterne-Brocot) a été construit de façon à simplifier au maximum la relation entre le développement de chaque rationnel père avec les développements de ses deux fils. D'un terme à l'autre de l'arbre, il y a des inversions et des additions entre numérateur et dénominateur. C'est exactement les opérations que l'on effectue lorsque l'on essaye de simplifier l'écriture d'une fraction continue.
Punaise je vais de découvertes en découvertes, qu'est-ce c'est con les maths !!
La racine de l'arbre binaire de Calkin-Wilf commence à .
La racine est le seul élément présent dans le premier niveau de l'arbre.
Le second niveau sera donc constitué des deux rationnels fils issus de la racine U(1)=1 dont les indices seront respectivement et 2 et 3.
Le troisième niveau sera donc constituer de 4 rationnels (les deux fils des deux éléments du niveau 2) et seront respectivement d'indice 4,5,6 et 7
Le quatrième niveau commence à 8, le cinquième à 16, et ainsi de suite ...
Par exemple:
Sur le quatrième niveau commençant à l'indice 8, et qui est composé de huit rationnels { 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1 }, les quatre premiers sont les fils (alternés petit et grand) des deux premiers rationnels du niveau précèdent { 1/3 3/2 2/3 3/1 }. La parité de l'indice (le bit b0) indique s'il s'agit d'un rationnel inférieur à l'unité (indices pairs) ou supérieur à l'unité (indices impairs). la rationnel 3/5 d'indice 10 est un rationnel inférieur à 1, c'est le troisième rationnel du quatrième niveau (position lue sur les premiers bits + 1).
Son père U(5) est au troisième niveau 5=%101b avec un indice impair (b0=1) il est donc plus grand que l'unité et se trouve en seconde position (deux dernier bit de n + 1) . Son grand-père est U(2) d'indice pair donc 1/2 < 1 premier des deux frères du seul groupe de ce niveau. Et son arrière-grand-père n'est rien d'autre que la racine U(1)=1/1.
L'indice est en quelque sorte sont héritage, c'est le code "génétique" qui décrit sa filiation, sa parité (dont s'il est <1 ou 1>) c'est à dire s'il est rattaché à la branche de gauche ou de droite de l'arbre.
U(10) 3/5 %1010b quatrième niveau, troisième position, cadet <1, branche de gauche
U(5) 3/2 %101b troisième niveau, seconde position, ainé 1> , branche de droite
U(2) 1/2 %10b second niveau , première position, cadet <1 , branche de gauche
U(1) 1/1 %1b racine qui n'a pas de code génétique i=%1b car le dernier bit du code indique simplement que l'on a commencé à compter à 1 (ce qui l'air de rien est un détail important qui permet de lire le code génétique , c'est à dire la position de u(n) dans l'arbre sans avoir à se préoccuper de retenues).
Vous comprenez la relation intime qu'il y a dans la séquence énumérant les rationnels, leur indice dans la suite U(n), la décomposition binaire de l'indice n, la position géographique de U(n) dans l'arbre et les propriétés du rapport a_n/b_n dont les numérateur et dénominateurs sont lié d'une branche à l'autre ?
C'est pure magie !
Ah! Oui vous aviez pas vu que les éléments de la suite proposé par gégé sont une alternance de rationnels inférieurs à 1 et supérieurs à 1. Le nombre de propriétés remarquables concernant ces arbres et ces suites est tout simplement hallucinant. Pour moi qui aime l'ordre , la symétrie, les nombres et les transformations, je suis en plein dans la matrice, je cours comme un fou après le lapin blanc au pays rêvé d'Alice.
L'algorithme basé sur les matrices, utilise un codage astucieux de chaque rationnel à l'aide d'une matrice carré 2x2 reprenant les numérateur et dénominateur des deux rationnels générateur. Oui, j'ai pas expliqué, mais pour être sûr que l'arbre (ou la suite) ne contienne qu'une seule fois chaque rationnel strictement positif sous sa forme irréductible, on utilise des suites de Farey et chaque rationnel est en réalité obtenu par une médiane entre deux points asymptotiques P2 et P1 qui ne peuvent faire partie de l'arbre (ou de la suite); A savoir vers la gauche la valeur zéro (matrice 0/1) et à droite l'infini (qui est exprimé sous la forme curieuse 1/0). La racine de l'arbre est exactement placée au milieu, sur la médiane .
Avec les matrices, La racine U(1)=1/1 est représentée par la matrice identité il est possible de calculer la valeur de U(n) en suivant le chemin au travers de l'arbre à l'aide d'une matrice de passage selon que l'on suit la branche de gauche (vers le plus petit des fils) ou la branche de droite (vers le plus grand des fils) à l'aide de deux matrices de passage respectivement G et D qui permettent de calculer la matrice représentant la nouvelle médiane du rationnel fils.
Mais il faut répéter l'opération à chaque niveau, toujours selon que l'on va vers la droite (vers l'infini) ou la gauche (vers le néant), c'est ce que fait le code d'avant-hier.
Pour calculer U(500), c'est plus rapide que de calculer les 499 éléments de la suite de Stern. Comme U(500) n'est pas très loin, il est quelque part au 9-ième niveau de l'arbre (en effet 500=%111110100b fait 9 bits de long).
Avec lecalcul utilisant les fractions continues, ce n'est plus les directions droite ou gauche qui entrent en jeu, mais le nombre de fois que l'on continue dans la même direction. Chaque fois que l'on change de direction, on effectue une inversion en plus de l'addition des termes. Quand on continue dans la même direction ne fait qu'additionner numérateur et dénominateur.
Ce qui fait que pour, par exemple, 500=% 11111 0 1 00 b est composé de 4 groupes de bits consécutifs identiques, il n'y a que quatre changement de direction gauche/droite. c'est donc encore plus court !
gégé a toujours de bonnes questions, je suis sûr qu'il connait tout cela par cœur et que c'est pour cela qu'il à propose cette suite U(n) !?
Quel magicien ! Quel guide d'agence de voyage rationnel infinitésimal multidimensionnel.
Par exemple, pour calculer U(500):
Et pour U(5000):
Et pour calculer U(1081):
D'où le code pour SHARP PC-1211:
Code : Tout sélectionner
1:CLEAR :INPUT N:B=1,D=2^INT (LOG N/LOG 2
2:R=1-R,F=A
3:IF D IF INT (N/D)=R LET N=N-RD,D=INT .5D,F=F+B:GOTO 3
4:A=B,B=F:IF D+R GOTO 2
5:BEEP 1:PRINT A,B
Registres:
N valeur de l'indice, pendant la décomposition la valeur de D est retirée de N pour tous les bits à 1.
D valeur binaire servant à décomposer l'indice; je fais varier D de 2^p à 0 par division par 2 avec p=INT(LOG2(N)).
Dans ce sens la décomposition et le calcul des fractions continues est plus facile.
R bit du groupe, comparé à INT(N/D)=R afin de compter la taille t des groupes de bits consécutivement à 1 ou 0
F calcul de la fraction continue. Chaque fois qu'un bit est compté, F est incrémenté de B
A/B registres contenant le rationnel U(N)=A/B, à chaque changement de groupe de t-bits les valeurs de A et B sont échangées F=A,A=B,B=F
En réalité ce revient à effectuer l'inversion et les additions A'←B, B'←A+t.B où t est le nombre de bits identiques.
Touts les bits sont testés (D est divisé par deux jusqu'à D=0). Lorsque D=0, les indices impairs sont détectés par R=1 (les indices pairs finissent avec R=0 lorsque D s'annule).
Le test D+R permet alors un tour de boucle supplémentaire qui inversera le rapport A/B afin d'obtenir U(n)=A/B plus grand que l'unité.
L'addition est utilise, le PC-1211 n'a pas d'opérateur OR.
Je suis en train de préparer la version pour HP-65
EDIT:
Pas facile pour moi de faire un truc court sur cette machine:
Registres:
R5:N valeur de l'indice, pendant la décomposition la valeur de D est retirée de N pour tous les bits à 1.
R4:D valeur binaire servant à décomposer l'indice D varie de 2^p à 0 où p est N log 2 LOG / INT
R3:R bit de groupe, comparé à INT(N/D)=R afin de compter la taille des groupe de bits consécutivement à 1 ou 0
R2:B
R1:A A/B registres contenant le rationnel U(N)=A/B, à chaque changement de groupe de t bits les valeurs de A et B sont échangées
Il n'y a pas de registre pour F, les incréments de B sont directement effectués dans A. Et l'échange se fait directement par l'intermédiaire de la pile entre R1:A et R2:B
Utilisation:
Saisir n et presser sur D pour lancer la détermination. A la fin du calcul le numérateur A est affiché, pressez R/S pour voir le dénominateur B.
Les labels A et B permettent d'afficher directement le numérateur A et le dénominateur B.
Le programme est long, il y une cinquantaine d'instructions qui ne sont pas toutes mergées, tout cela occupe 83 des 100 pas de programme disponibles. C'est moche pour un MPO. J'ai été surpris d'apprendre que même les pressions sur la touche préfixe 'f' sont enregistrées et comptent. Du coup, 100 pas sur cette machine, ce n'est pas énorme.
Mais c'est suffisant, elle a servie pour voyager jusqu'à la Lune, alors ce doit être bien.
Je compte sur les experts en machine classique pour améliorer ma piètre performance. Heureusement que certains lecteurs/enregistreurs de cartes magnétiques fonctionnent encore ! Danny aura peut-être la chance de ne pas avoir à tout retaper à chaque utilisation
Sur le listing, les nombres à trois chiffres sont les numéro de pas du programme jumeaux pour HP-15C. Je n'ai pas de HP-65 et donc j'ai utilisé mon HP-15C pour éprouver ce code. Avoir les cross-références sous les yeux peut être utile. En plus cela m'agace de ne pas avoir de n° d'instruction ce qui peut rendre d'éventuels remarques, notes ou commentaires concernant le code difficiles.
Je ne sait pas combien de temps met le calcul de U(500) avec ce programme. Pas sûr qu'il soit si rapide que cela. 81 instruction c'est beaucoup.
Ci-dessous le code pour HP-15C. Les registres sont exactement les mêmes. Mais dans ce code tout est mergé, presque à outrance.
500 f-D affiche 11 [R/S] 28 au bout de 24"23 sur une HP-15C lente mais vigoureuse.
5000 f-D donne 43 [R/S] 162 en moins de 42"