Termo Calkin–Wilf
O termo 5 da sequência de Calkin-Wilf é 3/2, alcançado a partir da raiz 1/1 com um passo à esquerda e outro à direita. Digite uma posição de 1 a um bilhão e receba a fração reduzida e o seu caminho. 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
- N
- 5
- Numerador
- 3
- Denominador
- 2
- Fração
- 3/2
- Caminho
- LR
A árvore de Calkin–Wilf é uma árvore binária completa cujos nós são exatamente os números racionais positivos, cada um uma única vez e em forma irredutível. Percorrer a árvore nível a nível (ou indexar os nós na ordem natural de heap binário que coincide com o caminho binário de um inteiro positivo n) produz uma enumeração clássica de Q+: a sequência de Calkin–Wilf. O índice um é a fração raiz um sobre um; cada índice posterior segue um único caminho esquerda-direita codificado pelos dígitos binários de n após o bit um inicial. Estudantes de combinatória enumerativa, matemática discreta e reconstrução racional precisam de um oráculo rápido que devolva numerador e denominador para um índice seguro arbitrário sem construir a árvore inteira. Esta capacidade aceita um inteiro positivo n, percorre esse caminho com algumas somas inteiras e devolve a fração reduzida a/b junto com uma string de caminho e uma fórmula curta.
O que é a enumeração de Calkin–Wilf e como se define a n-ésima fração
Neil Calkin e Herbert Wilf popularizaram uma árvore binária notavelmente simples de racionais positivos: a raiz é um sobre um; o filho esquerdo de uma fração a sobre b é a sobre (a mais b); o filho direito é (a mais b) sobre b. Todo racional positivo aparece exatamente uma vez, já em termos mínimos, de modo que a árvore é ao mesmo tempo uma enumeração de Q+ e uma forma canônica reduzida de cada valor.
O índice natural n com base em um rotula nós pela posição na ordem de heap binário completo: n igual a um é a raiz, n igual a dois é o filho esquerdo da raiz (um meio), n igual a três é o filho direito (dois sobre um), n igual a quatro é o neto esquerda-esquerda (um terço), e assim por diante.
De forma equivalente, escreva n em binário, descarte o bit um inicial que sempre marca a raiz e interprete cada bit restante do mais significativo ao menos como um movimento: zero significa esquerda, um significa direita. Após esses movimentos você obtém a única fração reduzida a/b naquele nó. Uma identidade clássica liga esse percurso à sequência diatômica de Stern s: a fração de Calkin–Wilf no índice n é s(n) sobre s(n mais um).
Como cada passo apenas soma dois inteiros positivos, o algoritmo é determinístico, leve em alocação e livre de arredondamento em ponto flutuante — ideal para oráculos de lição de casa, plugins LMS e cadernos de pesquisa que precisam de numeradores e denominadores exatos em vez de decimais aproximados.
Contrato de entrada, campos de resposta e comportamento de erro
Valores menores que um — incluindo zero e todo índice negativo — falham com mensagem clara de que o índice de Calkin–Wilf deve ser pelo menos um; essas falhas de validação não são cobradas. Em sucesso o corpo ecoa n, fornece numerator e denominator como inteiros positivos, fraction como string numerador barra denominador, formula como reafirmação curta das regras de raiz e filhos mais a regra do caminho binário, e path como as letras L e R dos movimentos após a raiz (ou a palavra root quando n é um).
Exemplo: n igual a um produz fração um barra um e path root. Exemplo: n igual a cinco tem binário um zero um, bits de caminho zero e depois um, logo esquerda e depois direita a partir de um sobre um dá três sobre dois, path LR. Exemplo: n igual a sete tem path RR e fração três sobre um.
Clientes que só precisam do racional podem ler fraction ou o par de inteiros; tutores podem mostrar path ao lado da resposta para que alunos auditem cada passo.
Onde o termo de Calkin–Wilf é útil
Cadernos de pesquisa que exploram representações hiperbinárias, demos da função interrogação de Minkowski ou estratégias de amostragem racional costumam precisar de um oráculo exato e rápido da n-ésima fração de Calkin–Wilf mantendo o resultado reduzido por construção. Ferramentas de engenharia e educação que geram racionais de teste positivos únicos para testes baseados em propriedades podem obter termos sucessivos por índice em vez de inventar pares aleatórios não reduzidos que depois exigem limpeza com gcd.
Mantenha pedidos pequenos, documente que n é um inteiro positivo a partir de um e trate numerator, denominator e fraction como campos canônicos de resposta em checagens automáticas.
Casos de uso
Verificações em sala e lição de casa
Permita que alunos enviem um índice positivo n e verifiquem a fração de Calkin–Wilf a/b pelas regras de filho esquerdo e direito, com a string de caminho visível para crédito parcial.
Correção automática em LMS e exames
Pontue itens de enumeração de Calkin–Wilf com um oráculo determinístico que rejeita n menor que um e nunca inventa racionais não reduzidos ou duplicados.
Racionais de teste positivos únicos
Gere um fluxo de racionais positivos reduzidos e distintos por índice para testes baseados em propriedades sem chamar gcd em pares aleatórios.
Perguntas frequentes
Como obter a n-ésima fração de Calkin–Wilf?
Envie um inteiro positivo n (n ≥ 1).
O que acontece se n for zero ou negativo?
O índice de Calkin–Wilf usado aqui é um inteiro positivo a partir de um; valores menores que um são rejeitados e não cobrados.
A fração devolvida está sempre reduzida?
Sim. Todo nó da árvore de Calkin–Wilf já está em termos mínimos, de modo que numerator e denominator são coprimos para todo n válido.
Qual a diferença em relação à sequência de Stern–Brocot?
A sequência diatômica de Stern devolve um único inteiro s(n). O termo de Calkin–Wilf é o racional s(n)/s(n+1) (equivalente ao percurso da árvore acima). A intenção de busca e a forma de saída diferem: fração versus valor diatômico.
O que significa o caminho com as letras L e R?
Escreva n em binário e tire o 1 inicial: cada 0 que sobra é um passo à esquerda e cada 1, um passo à direita a partir da raiz. Na posição 5, o binário 101 deixa os dígitos 0 e 1, então o caminho é LR e termina em 3/2.
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-term \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":5}'const res = await fetch("https://api.kit.forhosting.com/numth/calkin-wilf-term", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 5
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/calkin-wilf-term",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 5
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/calkin-wilf-term", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":5}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":5}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/calkin-wilf-term", 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
{
"n": 5
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.calkin_wilf_term",
"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
Índices menores que um são rejeitados com invalid_input para que corretores e scripts nunca tratem zero nem posições negativas como termos válidos.
O que é a enumeração de Calkin–Wilf e como se define a n-ésima fração
Este endpoint implementa o percurso direto da árvore em vez de uma tabela Stern separada, mas as respostas coincidem com essa identidade para todo n positivo.
Contrato de entrada, campos de resposta e comportamento de erro
Envie um corpo JSON com um único campo obrigatório n: um inteiro positivo maior ou igual a um, como número JSON ou como string de dígitos decimais, no máximo um bilhão. Os aliases index e order são aceitos com o mesmo significado. n ausente, strings vazias, não inteiros, números não finitos e valores acima do máximo falham com invalid_input indicando o problema. A implementação é parse pura de nível A: sem rede, sem tokens de modelo, sem sistema de arquivos, e o mesmo módulo pode rodar no caminho gratuito do navegador e no Worker de borda sem divergir.
Onde uma API do termo de Calkin–Wilf se paga
Cursos de combinatória enumerativa e matemática discreta usam a árvore de Calkin–Wilf ao ensinar bijeções entre inteiros positivos e racionais positivos, ligações com frações contínuas e comparações com a árvore de Stern–Brocot; uma API pequena permite que plugins LMS verifiquem respostas de alunos para n arbitrário sem embutir um sistema completo de álgebra computacional. Como cada chamada bem-sucedida custa o preço base publicado US$ 0,002 sem tokens de modelo e sem rede de saída, validação falha não consome saldo e o algoritmo é apenas O(log n) somas inteiras, você obtém frações reproduzíveis para lição de casa, correção e workers de borda sem infraestrutura pesada de teoria dos números.
Perguntas técnicas
Quanto custa a calculadora do termo de Calkin–Wilf?
A ferramenta do navegador é gratuita. Pedidos API usam saldo KIT pré-pago a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.