Sequência Q de Hofstadter
Na sequência Q de Hofstadter, o 10º termo vale 6 e o 20º vale 12. Cada termo novo olha para trás a distâncias decididas pelos anteriores, por isso ela cresce de forma irregular; aqui você obtém qualquer termo até o índice cem mil. 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
- 10
- Q
- 6
- Recorrência
- Q(1)=Q(2)=1; Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) for n>2
A sequência Q de Hofstadter é uma célebre recorrência meta-Fibonacci de Gödel, Escher, Bach: cada termo consulta termos anteriores usando outros termos como deslocamentos. Com sementes Q de um e Q de dois iguais a um, a regra para todo índice maior é Q de n igual a Q de n menos Q de n menos um, mais Q de n menos Q de n menos dois. A sucessão começa um, um, dois, três, três, quatro, cinco, cinco, seis, seis, e cresce de forma irregular perto de n sobre dois em média.
O que é a sequência Q de Hofstadter e como a recorrência funciona
Douglas Hofstadter introduziu a sequência Q como uma prima caótica de Fibonacci em que os argumentos das chamadas recursivas dependem de valores já calculados e não de defasagens fixas. As sementes clássicas são Q de um igual a um e Q de dois igual a um. Para todo inteiro n maior que dois, a definição é Q de n igual a Q de n menos Q de n menos um, mais Q de n menos Q de n menos dois.
Ao desenrolar os primeiros passos obtêm-se dois, três, três, quatro, cinco, cinco, seis, seis, seis, oito, oito, oito, dez, e assim por diante. Diferente de Fibonacci, que sempre soma os dois predecessores imediatos, Q usa esses predecessores como deslocamentos dentro da própria sucessão, de modo que o crescimento não é monótono em forma fechada simples e os termos oscilam em torno de uma tendência linear. A sequência está catalogada como OEIS A005185 sob a indexação baseada em um usada aqui.
Dicas práticas, limites e onde a sequência Q se encaixa
Alunos encontram a sequência Q de Hofstadter ao estudar definições recursivas que não são recorrências lineares de coeficientes constantes, ao comparar famílias meta-Fibonacci e ao explorar como uma regra autorreferencial simples pode produzir comportamento local irregular e ainda permanecer bem definida para todo inteiro positivo. Professores podem gerar gabaritos para folhas que pedem Q de um n dado sem confiar em calculadoras opacas que escondem as sementes.
Desenvolvedores usam o mesmo contrato para validar dados de amostra de bibliotecas de teoria dos números, semear testes de propriedade ou pré-calcular termos esperados antes de uma demonstração. A prática de concursos muitas vezes precisa de uma fonte rápida offline de valores Q para checar soluções sem baixar tabelas OEIS sob pressão de tempo.
Não confunda o Q de um baseado em um igual a um com deslocamentos de tabela baseados em zero de alguns exemplos de código: confira sempre as sementes do campo recurrence antes de avaliar contra outra convenção.
Casos de uso
Checagens de Q(n) em lições e concursos
Calcule a Q de Hofstadter de n para folhas de exercício e validadores de concurso sem tabelas longas de recorrência manual nem scripts improvisados.
Ensino de recorrências meta-Fibonacci
Mostre aos alunos como uma regra de deslocamento autorreferencial difere de Fibonacci enquanto eles mudam n ao vivo no navegador sem custo.
Perguntas frequentes
O que acontece se n estiver abaixo de 1?
A sequência Q de Hofstadter é definida aqui apenas para inteiros positivos n ≥ 1.
Como Q(n) é calculado?
As sementes são Q(1)=Q(2)=1. Para cada k de 3 até n o motor define Q(k)=Q(k−Q(k−1))+Q(k−Q(k−2)) com um arranjo inteiro bottom-up. O mesmo n sempre produz o mesmo q.
Quais são alguns valores conhecidos?
Q(1)=1, Q(2)=1, Q(3)=2, Q(4)=3, Q(5)=3, Q(6)=4, Q(10)=6, Q(20)=12. A sucessão é OEIS A005185 sob esta indexação baseada em 1.
Qual a diferença entre a sequência Q e a de Fibonacci?
A de Fibonacci soma os dois termos anteriores. A sequência Q usa esses dois termos como distâncias para olhar para trás e soma os termos encontrados ali. Por isso cresce de forma irregular, em média perto de n/2.
Qual é o maior índice aceito?
Pode pedir qualquer termo de 1 até cem mil. Os dois primeiros termos valem 1 e a numeração segue o catálogo OEIS A005185; tabelas que começam em zero ficam deslocadas uma posição.
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/hofstadter-q \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":10}'const res = await fetch("https://api.kit.forhosting.com/numth/hofstadter-q", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 10
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/hofstadter-q",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 10
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/hofstadter-q", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":10}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":10}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/hofstadter-q", 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": 10
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.hofstadter_q",
"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
Esta capacidade devolve o valor Q exato do n-ésimo termo como JSON determinístico—sem solver simbólico, sem chute em ponto flutuante, sem chamada de rede—para que corretores de lição, cruzamentos com OEIS, validadores de concurso e demonstrações didáticas vejam o mesmo inteiro puro no executor gratuito do navegador e no caminho de API pré-paga a US$ 0,002 por solicitação bem-sucedida.
O que é a sequência Q de Hofstadter e como a recorrência funciona
Quando você só precisa de um termo, envie o índice n; a resposta ecoa n, o valor q igual a Q de n, uma string de fórmula curta e um resumo da recorrência que documenta as sementes e a regra para que avaliadores e alunos possam recalcular casos pequenos à mão e confrontar a API linha a linha sem ambiguidade sobre a convenção de indexação.
Como chamar a API e o que a resposta contém
Uma resposta bem-sucedida inclui n ecoado, q igual a Q de n, formula com a string Q de n igual a Q de n menos Q de n menos um mais Q de n menos Q de n menos dois, e recurrence documentando Q de um igual a Q de dois igual a um e a regra para n maior que dois. Prefira exemplos de sala emparelhados como n igual a um resultando em um, n igual a dez resultando em seis, n igual a vinte resultando em doze, e um n zero ou negativo demonstrando o rejeição rígida. Envie um corpo JSON com um único campo obrigatório n: um inteiro positivo de pelo menos um e no máximo cem mil, o índice baseado em um do termo Q desejado. Os aliases index, order e term são aceitos com o mesmo significado para que formulários, planilhas e query strings reutilizem um só contrato. Validação falha—n ausente, não inteiro, fração, notação científica, valor acima do limite publicado ou qualquer n abaixo de um—retorna invalid_input e nunca é cobrada. O preço é um fixo de US$ 0,002 por solicitação bem-sucedida com unidade item.
Dicas práticas, limites e onde a sequência Q se encaixa
Nesta página o trabalho roda inteiramente no seu navegador; pela API cada consulta bem-sucedida custa US$ 0,002, validação falha não é cobrada e nada é armazenado após a resposta. Limite n a cem mil para manter memória e tempo do Worker limitados; Q de n cresce aproximadamente como n sobre dois e permanece um inteiro seguro nesse intervalo. Combine esta página com Fibonacci, Padovan, Collatz e outras ferramentas de sucessões ao montar um pequeno laboratório recreativo de teoria dos números com endpoints gratuitos e determinísticos.
Casos de integração
Fixtures de teste determinísticos
Gere valores Q reproduzíveis para testes unitários, checagens de propriedade e asserções de CI que fixam índices conhecidos e termos esperados.
Perguntas técnicas
Quanto custa a calculadora da sequência Q de Hofstadter?
É grátis no seu navegador nesta página. Pela API, uma solicitação bem-sucedida custa US$ 0,002; entradas inválidas não são cobradas.
O algoritmo é aleatório?
Não. Usa apenas aritmética inteira determinística. Não há rede, não há Date e não há Math.random.