L'arbre de Calkin et Wilf
Description
L'arbre de Calkin & Wilf est une bijection entre l'ensemble des entiers positifs et l'ensemble des fractions positives réduites. Chaque entier positif correspond à une et une seule fraction positive réduite. Et chaque fraction positive réduite correspond à un et un seul entier positif. Le document ci-joint Calkin-Wilf.pdf résume l'essentiel.
Les fractions qui ne sont pas positives et les fractions positives qui ne sont pas réduites sont absentes de l'arbre et n'ont pas de nombre entier correspondant. Pour chaque fraction positive qui n'est pas réduite on pourrait lui associer la fraction positive réduite ayant la même valeur en divisant le numérateur et le dénominateur par leur pgcd mais ce n'est pas approprié : toutes les fractions positives réduites et seulement celles-ci y sont disponibles. L'arbre de Calkin & Wilf permet de démontrer que l'ensemble infini des fractions positives réduites est dénombrable.
Le programme ci-joint montre comment calculer et afficher d'une part la fraction positive réduite dont le numérateur et le dénominateur sont deux entiers de type int correspondant à un entier positif donné de type int64_t et d'autre part l'entier positif de type int64_t correspondant à une fraction positive réduite donnée dont le numérateur et le dénominateur sont deux entiers de type int. On peut noter que toutes les premières fractions sont de taille petite mais il y a des fractions de taille petite qui ont un rang élévé : par exemples, la fraction 1/n a pour rang 2^(n-1) et l'entier n, ou fraction n/1, a pour rang (2^n)-1. Il en résulte que dans certains cas la correspondance recherchée est en dehors des limites des entiers utilisés et c'est détecté et signalé : des exemples le montrent. Les calculs nécessaires ont toujours une durée brève d'exécution tant qu'on utilise les entiers indiqués.
Ce code est programmé avec Visual Studio Express 2012 pour Windows Desktop. Il affiche le résultat dans la console Windows. Si vous ne souhaitez pas refaire la compilation le fichier out.txt montre le résultat affiché.
Une variante de ce code est possible avec une bibliothèque comme GMP pour aller plus loin avec les entiers utilisables. Mais il est impossible de traiter l'ensemble complet parce qu'il est infini.
Merci pour vos remarques éventuelles.
Les fractions qui ne sont pas positives et les fractions positives qui ne sont pas réduites sont absentes de l'arbre et n'ont pas de nombre entier correspondant. Pour chaque fraction positive qui n'est pas réduite on pourrait lui associer la fraction positive réduite ayant la même valeur en divisant le numérateur et le dénominateur par leur pgcd mais ce n'est pas approprié : toutes les fractions positives réduites et seulement celles-ci y sont disponibles. L'arbre de Calkin & Wilf permet de démontrer que l'ensemble infini des fractions positives réduites est dénombrable.
Le programme ci-joint montre comment calculer et afficher d'une part la fraction positive réduite dont le numérateur et le dénominateur sont deux entiers de type int correspondant à un entier positif donné de type int64_t et d'autre part l'entier positif de type int64_t correspondant à une fraction positive réduite donnée dont le numérateur et le dénominateur sont deux entiers de type int. On peut noter que toutes les premières fractions sont de taille petite mais il y a des fractions de taille petite qui ont un rang élévé : par exemples, la fraction 1/n a pour rang 2^(n-1) et l'entier n, ou fraction n/1, a pour rang (2^n)-1. Il en résulte que dans certains cas la correspondance recherchée est en dehors des limites des entiers utilisés et c'est détecté et signalé : des exemples le montrent. Les calculs nécessaires ont toujours une durée brève d'exécution tant qu'on utilise les entiers indiqués.
Ce code est programmé avec Visual Studio Express 2012 pour Windows Desktop. Il affiche le résultat dans la console Windows. Si vous ne souhaitez pas refaire la compilation le fichier out.txt montre le résultat affiché.
Source :
// L'arbre de Calkin & Wilf est une bijection entre N* et une partie de N* x N*
// c'est à dire entre entre les entiers positifs : {1, 2, 3, 4, 5, 6, 7, ...}
// et les fractions positives réduites : {1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...}
// Voir : https://fr.wikipedia.org/wiki/Arbre_de_Calkin-Wilf
// ou : https://www.math.upenn.edu/~wilf/website/recounting.pdf
# include<iostream>
# include<iomanip>
# include<cstdint>
# include<vector>
bool fracVal(int64_t n, int frac[2]) {
if(n > 1) fracVal(n/2, frac);
if(frac[~n&1] > (INT_MAX - frac[n&1])) return false;
frac[~n&1] += frac[n&1];
return true;
}
bool niemeFrac(int64_t n, int frac[2]) {
if(!(n > 0)) return false;
frac[0] = 0;
frac[1] = 1;
if(fracVal(n, frac)) return true;
return false;
}
int pgcd(int a, int b) {
int r;
while(b != 0) {
r = a%b;
a = b;
b = r;
}
return a;
}
bool findFrac(int64_t &n, int p, int q) {
if(!(p>0 && q>0)) return false;
if(pgcd(p, q) != 1) return false;
std::vector<bool> vect;
while(!(p==1 && q==1)) {
if(p > q) {
vect.push_back(true);
p = p - q;
}
else {
vect.push_back(false);
q = q - p;
}
}
n = 1;
unsigned int j = vect.size();
for(unsigned int i=0; i<j; i++) {
if(n > (INTMAX_MAX - (n+1))) return false;
if(vect[j-i-1]) n = 2*n + 1;
else n = 2*n;
}
return true;
}
Conclusion
L'arbre de Calkin & Wilf ressemble à l'arbre de Stern & Brocot dont certaines propriétés sont différentes mais ils ont tous les deux des utilisations analogues.Une variante de ce code est possible avec une bibliothèque comme GMP pour aller plus loin avec les entiers utilisables. Mais il est impossible de traiter l'ensemble complet parce qu'il est infini.
Merci pour vos remarques éventuelles.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.