Terme Calkin–Wilf

L'arbre de Calkin–Wilf est un arbre binaire complet dont les nœuds sont exactement les nombres rationnels positifs, chacun une seule fois et sous forme irréductible. Parcourir l'arbre niveau par niveau (ou indexer les nœuds dans l'ordre naturel de tas binaire qui coïncide avec le chemin binaire d'un entier positif n) donne une énumération célèbre de Q+ : la suite de Calkin–Wilf. L'indice un est la fraction racine un sur un ; chaque indice suivant suit un unique chemin gauche-droite codé par les chiffres binaires de n après le bit un initial. Les étudiants en combinatoire énumérative, mathématiques discrètes et reconstruction rationnelle ont besoin d'un oracle rapide qui renvoie numérateur et dénominateur pour un indice sûr arbitraire sans construire tout l'arbre. Cette capacité accepte un entier positif n, parcourt ce chemin avec quelques additions entières et renvoie la fraction réduite a/b avec une chaîne de chemin et une courte formule.

Ce qu'est l'énumération de Calkin–Wilf et comment la n-ième fraction est définie

Neil Calkin et Herbert Wilf ont popularisé un arbre binaire remarquablement simple de rationnels positifs : la racine est un sur un ; le fils gauche d'une fraction a sur b est a sur (a plus b) ; le fils droit est (a plus b) sur b. Tout rationnel positif apparaît exactement une fois, déjà sous forme irréductible, de sorte que l'arbre est à la fois une énumération de Q+ et une forme canonique réduite de chaque valeur.

L'indice naturel n à base un étiquette les nœuds par leur position dans l'ordre de tas binaire complet : n égal à un est la racine, n égal à deux est le fils gauche de la racine (un demi), n égal à trois est le fils droit (deux sur un), n égal à quatre est le petit-fils gauche-gauche (un tiers), et ainsi de suite.

De façon équivalente, écrivez n en binaire, supprimez le bit un initial qui marque toujours la racine, et interprétez chaque bit restant du plus significatif au moins comme un déplacement : zéro signifie gauche, un signifie droite. Après ces déplacements vous obtenez l'unique fraction réduite a/b en ce nœud. Une identité classique relie ce parcours à la suite diatomique de Stern s : la fraction de Calkin–Wilf à l'indice n est s(n) sur s(n plus un).

Ce point d'accès implémente le parcours direct de l'arbre plutôt qu'une table Stern séparée, mais les réponses coïncident avec cette identité pour tout n positif. Comme chaque étape n'additionne que deux entiers positifs, l'algorithme est déterministe, léger en allocation et sans arrondi flottant — idéal pour des oracles de devoirs, plugins LMS et carnets de recherche qui exigent numérateurs et dénominateurs exacts plutôt que des décimales approximatives.

Contrat d'entrée, champs de réponse et comportement d'erreur

Les valeurs inférieures à un — y compris zéro et tout indice négatif — échouent avec un message clair indiquant que l'indice de Calkin–Wilf doit être au moins un ; ces échecs de validation ne sont pas facturés.

En cas de succès le corps renvoie n, fournit numerator et denominator comme entiers positifs, fraction comme chaîne numérateur barre dénominateur, formula comme bref rappel des règles de racine et d'enfants plus la règle du chemin binaire, et path comme les lettres L et R des déplacements après la racine (ou le mot root lorsque n vaut un). Exemple : n égal à un donne la fraction un barre un et path root.

Exemple : n égal à cinq a le binaire un zéro un, bits de chemin zéro puis un, donc gauche puis droite depuis un sur un donne trois sur deux, path LR. Exemple : n égal à sept a path RR et fraction trois sur un. Les clients qui n'ont besoin que du rationnel peuvent lire fraction ou la paire d'entiers ; les tuteurs peuvent afficher path à côté de la réponse pour que les étudiants vérifient chaque pas.

Où le terme de Calkin–Wilf est utile

Les carnets de recherche qui explorent les représentations hyperbinaires, les démonstrations de la fonction point d'interrogation de Minkowski ou les stratégies d'échantillonnage rationnel ont souvent besoin d'un oracle exact et rapide de la n-ième fraction de Calkin–Wilf en gardant le résultat réduit par construction. Les outils d'ingénierie et d'éducation qui génèrent des rationnels de test positifs uniques pour des tests basés sur les propriétés peuvent tirer des termes successifs par indice au lieu d'inventer des paires aléatoires non réduites qui exigent ensuite un nettoyage par gcd.

Gardez les requêtes petites, documentez que n est un entier positif commençant à un, et traitez numerator, denominator et fraction comme champs de réponse canoniques pour les contrôles automatiques.