Índice Calkin-Wilf
A fração 3/2 ocupa a 5.ª posição na sequência de Calkin-Wilf, dois níveis abaixo da raiz 1/1. Digite uma fração reduzida com numerador e denominador de 1 a um milhão e receba a posição exata e a profundidade. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- A
- 3
- B
- 2
- Fração
- 3/2
- Índice
- 5
- Profundidade
- 2
- Gcd
- 1
A árvore de Calkin-Wilf enumera cada número racional positivo exatamente uma vez como fração reduzida a sobre b. Estudantes de matemática discreta, combinatória enumerativa e frações contínuas costumam precisar do índice de uma fração dada nessa sequência — o rótulo em largura do nó da árvore que carrega a/b. Esta capacidade aceita dois inteiros positivos a e b, verifica se a fração já está em termos mínimos e devolve o índice Calkin-Wilf com base um junto com a profundidade do caminho a partir da raiz um-sobre-um.
O que a sequência de Calkin-Wilf atribui a cada fração reduzida
A árvore de Calkin-Wilf é uma árvore binária enraizada cuja raiz é rotulada um sobre um. O filho esquerdo de um nó rotulado a sobre b é a sobre a mais b, e o filho direito é a mais b sobre b. Todo racional positivo aparece em exatamente um nó quando escrito em termos mínimos, por isso a enumeração é uma listagem perfeita de Q-plus e não um percurso multivalorado por equivalentes como dois quartos.
Ler a árvore na ordem natural de heap — índice da raiz um, filho esquerdo de n em dois n, filho direito em dois n mais um — produz a sequência de Calkin-Wilf: um sobre um, um sobre dois, dois sobre um, um sobre três, três sobre dois, dois sobre três, três sobre um, e assim por diante.
Dado um par reduzido a e b, esta ferramenta reconstrói o caminho único de a sobre b de volta à raiz aplicando repetidamente a regra do pai: se a é menor que b o nó era filho esquerdo e o pai é a sobre b menos a; se a é maior que b era filho direito e o pai é a menos b sobre b. Codificar esse caminho como índice binário recupera a posição na sequência sem gerar a árvore inteira.
A profundidade é o número de arestas a partir da raiz, útil quando importa a altura mais do que o rótulo binário denso.
Casos de uso
Verificações em sala e lição de casa
Permita que os alunos enviem a e b reduzidos e verifiquem o índice Calkin-Wilf com base um e a profundidade do caminho em relação aos desenhos do livro.
Provas e correção automática LMS
Corrija itens de índice Calkin-Wilf com um oráculo determinístico que rejeita frações não reduzidas em vez de simplificar em silêncio.
Cadernos de pesquisa e demos de bijeção
Mapeie racionais positivos a naturais via o rotulamento Calkin-Wilf em scripts sem embutir uma biblioteca completa de álgebra computacional.
Perguntas frequentes
Como obtenho o índice Calkin-Wilf de uma fração a/b?
Envie inteiros positivos a e b com gcd(a,b)=1.
O que acontece se a fração não estiver em termos mínimos?
Os rótulos Calkin-Wilf são únicos para positivos reduzidos; entrada não reduzida é rejeitada e não cobrada. Reduza primeiro e tente de novo.
O índice é de base zero ou de base um?
De base um: 1/1 tem índice 1, 1/2 tem índice 2, 2/1 tem índice 3, conforme a numeração habitual de heap da árvore.
Como isso difere da árvore de Stern-Brocot?
Ambas as árvores enumeram positivos, mas as regras de filhos e a ordem diferem.
O que a profundidade de uma fração indica?
Ela conta os passos da raiz 1/1 até a fração. A fração 3/2 tem profundidade 2, porque é o filho direito de 1/2, que por sua vez é o filho esquerdo da raiz.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
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)Exemplo de requisição
{
"a": 3,
"b": 2
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.calkin_wilf_index",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Entradas não reduzidas falham com invalid_input para que a bijeção entre posições e positivos reduzidos permaneça exata.
O que a sequência de Calkin-Wilf atribui a cada fração reduzida
Como o mapa é bijetivo sobre positivos reduzidos, pedir o índice de uma fração não reduzida quebraria a unicidade; a API portanto rejeita gcd maior que um em vez de reduzir em silêncio e devolver a posição de outro rótulo.
Contrato de entrada, forma da resposta e comportamento de erro
Essa falha não é cobrada. Exemplo: a igual a três e b igual a dois produz a fração três sobre dois, índice cinco e profundidade dois, porque três sobre dois é o filho direito de um sobre dois, que é o filho esquerdo da raiz. Envie por POST um corpo JSON com dois inteiros positivos obrigatórios: a, o numerador, e b, o denominador. Os aliases numerator, num e p são aceitos para a; denominator, den e q para b. Cada campo pode chegar como número JSON ou como string decimal inteira; zeros à esquerda, frações, notação científica, zero e negativos falham com invalid_input nomeando o campo. Os valores devem estar entre um e um milhão inclusive para manter o custo do percurso limitado no Worker. No sucesso o corpo ecoa a e b, uma string de fração como três barra dois, o índice como número JSON quando cabe no intervalo de inteiros seguros ou como string decimal quando não, a profundidade do caminho a partir da raiz, gcd igual a um e uma fórmula curta reafirmando as regras de filho esquerdo e direito. Combine a resposta com seu próprio desenho da árvore se precisar de um diagrama; este endpoint devolve apenas o índice e a profundidade e não emite listas de pais intermediários além do que você pode recalcular com as mesmas regras.
Onde uma API de índice Calkin-Wilf agrega valor
Cursos de matemática discreta e plataformas de preparação para competições usam uma calculadora de índice Calkin-Wilf para que aprendizes verifiquem a posição de racionais reduzidos arbitrários sem desenhar árvores grandes à mão. Cadernos de pesquisa que estudam representações hiperbinárias, mapas ligados ao ponto de interrogação de Minkowski ou bijeções entre N e Q-plus precisam de um oráculo determinístico que recuse entrada não reduzida em vez de simplificar em silêncio e se afastar da definição do livro. Geradores de currículo e corretores automáticos LMS podem marcar itens que pedem o índice de três meios ou cinco oitavos com uma única chamada API ao preço base publicado US$ 0,002, com casos de gcd inválido sem cobrança.
Perguntas técnicas
Quanto custa a calculadora de índice de fração Calkin-Wilf?
A ferramenta no navegador é gratuita. Requisições API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.