Indice Calkin-Wilf
La fraction 3/2 est la 5e de la suite de Calkin-Wilf, deux niveaux sous la racine 1/1. Saisissez une fraction irréductible dont le numérateur et le dénominateur vont de 1 à un million pour obtenir sa position exacte et sa profondeur. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- A
- 3
- B
- 2
- Fraction
- 3/2
- Indice
- 5
- Profondeur
- 2
- Gcd
- 1
L'arbre de Calkin-Wilf énumère chaque nombre rationnel positif exactement une fois sous forme de fraction réduite a sur b. Les étudiants en mathématiques discrètes, combinatoire énumérative et fractions continues ont souvent besoin de l'indice d'une fraction donnée dans cette suite — l'étiquette en largeur du nœud de l'arbre qui porte a/b. Cette capacité accepte deux entiers positifs a et b, vérifie que la fraction est déjà sous forme irréductible, et renvoie l'indice Calkin-Wilf en base un avec la profondeur du chemin depuis la racine un-sur-un.
Ce que la suite de Calkin-Wilf assigne à chaque fraction réduite
L'arbre de Calkin-Wilf est un arbre binaire enraciné dont la racine est étiquetée un sur un. L'enfant gauche d'un nœud étiqueté a sur b est a sur a plus b, et l'enfant droit est a plus b sur b. Tout rationnel positif apparaît en exactement un nœud lorsqu'il est écrit sous forme irréductible, c'est pourquoi l'énumération est un listage parfait de Q-plus plutôt qu'un parcours multivalué d'équivalents comme deux quarts.
Lire l'arbre dans l'ordre naturel de tas — indice racine un, enfant gauche de n en deux n, enfant droit en deux n plus un — produit la suite de Calkin-Wilf : un sur un, un sur deux, deux sur un, un sur trois, trois sur deux, deux sur trois, trois sur un, et ainsi de suite.
Étant donné une paire réduite a et b, cet outil reconstruit le chemin unique de a sur b vers la racine en appliquant de façon répétée la règle du parent : si a est inférieur à b le nœud était un enfant gauche et le parent est a sur b moins a ; si a est supérieur à b c'était un enfant droit et le parent est a moins b sur b. Encoder ce chemin en indice binaire retrouve la position dans la suite sans générer l'arbre entier.
La profondeur est le nombre d'arêtes depuis la racine, utile lorsque vous vous souciez de la hauteur plutôt que de l'étiquette binaire dense.
Où l'indice Calkin-Wilf est utile
Les cours de mathématiques discrètes et les plateformes de préparation aux concours utilisent un calculateur d'indice Calkin-Wilf pour que les apprenants vérifient la position de rationnels réduits arbitraires sans dessiner de grands arbres à la main. Les carnets de recherche qui étudient les représentations hyperbinaires, les cartes liées au point d'interrogation de Minkowski ou les bijections entre N et Q-plus ont besoin d'un oracle déterministe qui refuse une entrée non réduite plutôt que de simplifier en silence et de s'écarter de la définition du manuel.
Comme l'implémentation est pure parse de niveau A, chaque appel réussi évite les jetons de modèle et le réseau sortant.
Cas d’usage
Vérifications en classe et devoirs
Laissez les élèves envoyer a et b réduits et vérifier l'indice Calkin-Wilf en base un et la profondeur du chemin par rapport aux dessins du manuel.
Examens et notation automatique LMS
Notez les items d'indice Calkin-Wilf avec un oracle déterministe qui rejette les fractions non réduites au lieu de simplifier en silence.
Carnets de recherche et démos de bijection
Mappez les rationnels positifs vers les naturels via l'étiquetage Calkin-Wilf dans des scripts sans embarquer une bibliothèque complète d'algèbre informatique.
Questions fréquentes
Comment obtenir l'indice Calkin-Wilf d'une fraction a/b ?
Envoyez des entiers positifs a et b avec gcd(a,b)=1.
Que se passe-t-il si la fraction n'est pas sous forme irréductible ?
Les étiquettes Calkin-Wilf sont uniques pour les positifs réduits ; l'entrée non réduite est rejetée et non facturée. Réduisez d'abord, puis réessayez.
L'indice est-il en base zéro ou en base un ?
En base un : 1/1 a l'indice 1, 1/2 a l'indice 2, 2/1 a l'indice 3, selon la numérotation habituelle en tas de l'arbre.
En quoi cela diffère-t-il de l'arbre de Stern-Brocot ?
Les deux arbres énumèrent les positifs, mais les règles d'enfants et l'ordre diffèrent.
Qu'indique la profondeur d'une fraction ?
Elle compte les étapes entre la racine 1/1 et la fraction. La fraction 3/2 a une profondeur de 2, car elle est l'enfant droit de 1/2, lui-même enfant gauche de la racine.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre stack
curl -X POST https://api.kit.forhosting.com/numth/calkin-wilf-index \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":3,"b":2}'const res = await fetch("https://api.kit.forhosting.com/numth/calkin-wilf-index", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 3,
"b": 2
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/calkin-wilf-index",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 3,
"b": 2
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/calkin-wilf-index", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":3,"b":2}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":3,"b":2}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/calkin-wilf-index", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemple de requête
{
"a": 3,
"b": 2
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.calkin_wilf_index",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Les entrées non réduites échouent avec invalid_input afin que la bijection entre positions et positifs réduits reste exacte.
Ce que la suite de Calkin-Wilf assigne à chaque fraction réduite
Comme la carte est bijective sur les positifs réduits, demander l'indice d'une fraction non réduite briserait l'unicité ; l'API rejette donc un gcd supérieur à un au lieu de réduire en silence et de renvoyer la position d'une autre étiquette.
Contrat d'entrée, forme de la réponse et comportement d'erreur
Après l'analyse, le gestionnaire calcule le gcd de a et b ; si ce gcd n'est pas exactement un, la tâche échoue avec un message indiquant que la fraction n'est pas sous forme irréductible et suggérant la forme réduite a divisé par g sur b divisé par g. Cet échec n'est pas facturé. Exemple : a égal à trois et b égal à deux donne la fraction trois sur deux, l'indice cinq et la profondeur deux, car trois sur deux est l'enfant droit de un sur deux, lui-même enfant gauche de la racine. Associez la réponse à votre propre dessin d'arbre si vous avez besoin d'un schéma ; ce point de terminaison renvoie uniquement l'indice et la profondeur et n'émet pas de listes de parents intermédiaires au-delà de ce que vous pouvez recalculer avec les mêmes règles. Envoyez en POST un corps JSON avec deux entiers positifs obligatoires : a, le numérateur, et b, le dénominateur. Les alias numerator, num et p sont acceptés pour a ; denominator, den et q pour b. Chaque champ peut arriver comme nombre JSON ou comme chaîne décimale entière ; zéros en tête, fractions, notation scientifique, zéro et négatifs échouent avec invalid_input en nommant le champ. Les valeurs doivent être comprises entre un et un million inclus pour borner le coût du parcours sur le Worker. En cas de succès le corps renvoie a et b, une chaîne de fraction telle que trois barre deux, l'indice comme nombre JSON lorsqu'il tient dans la plage des entiers sûrs ou comme chaîne décimale sinon, la profondeur du chemin depuis la racine, gcd égal à un, et une courte formule rappelant les règles d'enfant gauche et droit.
Où une API d'indice Calkin-Wilf trouve son utilité
Les générateurs de cursus et les correcteurs automatiques LMS peuvent noter des items demandant l'indice de trois demis ou cinq huitièmes avec un seul appel API au prix de base publié $0.002, les cas de gcd invalide étant gratuits.
Questions techniques
Combien coûte le calculateur d'indice de fraction Calkin-Wilf ?
L'outil navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; l'entrée invalide n'est pas facturée.