Suite Q de Hofstadter
Dans la suite Q de Hofstadter, le 10e terme vaut 6 et le 20e vaut 12. Chaque nouveau terme regarde en arrière à des distances choisies par les précédents, d’où une croissance irrégulière ; obtenez ici tout terme jusqu’au rang cent mille. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- N
- 10
- Q
- 6
- Récurrence
- Q(1)=Q(2)=1; Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) for n>2
La suite Q de Hofstadter est une célèbre récurrence méta-Fibonacci issue de Gödel, Escher, Bach : chaque terme interroge des termes antérieurs en utilisant d'autres termes comme décalages. Avec les germes Q de un et Q de deux égaux à un, la règle pour tout indice plus grand est Q de n égal à Q de n moins Q de n moins un, plus Q de n moins Q de n moins deux. La suite commence par un, un, deux, trois, trois, quatre, cinq, cinq, six, six, et croît de façon irrégulière près de n sur deux en moyenne.
Qu'est-ce que la suite Q de Hofstadter et comment la récurrence fonctionne
Douglas Hofstadter a introduit la suite Q comme une cousine chaotique de Fibonacci où les arguments des appels récursifs dépendent de valeurs déjà calculées plutôt que de retards fixes. Les germes classiques sont Q de un égal à un et Q de deux égal à un. Pour tout entier n supérieur à deux, la définition est Q de n égal à Q de n moins Q de n moins un, plus Q de n moins Q de n moins deux.
En déroulant les premières étapes on obtient deux, trois, trois, quatre, cinq, cinq, six, six, six, huit, huit, huit, dix, et ainsi de suite. Contrairement à Fibonacci, qui additionne toujours les deux prédécesseurs immédiats, Q utilise ces prédécesseurs comme décalages dans la suite elle-même, de sorte que la croissance n'est pas monotone sous une forme fermée simple et que les termes oscillent autour d'une tendance linéaire. La suite est répertoriée comme OEIS A005185 sous l'indexation partant de un utilisée ici.
Conseils pratiques, limites et place de la suite Q
Les élèves rencontrent la suite Q de Hofstadter en étudiant des définitions récursives qui ne sont pas des récurrences linéaires à coefficients constants, en comparant des familles méta-Fibonacci et en explorant comment une règle auto-référentielle simple peut produire un comportement local irrégulier tout en restant bien définie pour tout entier positif. Les enseignants peuvent générer des corrigés pour des feuilles demandant Q d'un n donné sans se fier à des calculatrices opaques qui masquent les germes.
Les développeurs utilisent le même contrat pour valider des données d'exemple de bibliothèques de théorie des nombres, amorcer des tests de propriétés ou précalculer des termes attendus avant une démonstration. La préparation aux concours a souvent besoin d'une source rapide hors ligne de valeurs Q pour vérifier des solutions sans télécharger des tables OEIS sous contrainte de temps.
Ne confondez pas le Q de un partant de un égal à un avec des décalages de tableau partant de zéro de certains exemples de code : vérifiez toujours les germes du champ recurrence avant de noter par rapport à une autre convention.
Cas d’usage
Vérifications de Q(n) pour devoirs et concours
Calculez la Q de Hofstadter de n pour des feuilles d'exercices et des validateurs de concours sans longues tables de récurrence manuelles ni scripts improvisés.
Enseignement des récurrences méta-Fibonacci
Montrez aux élèves comment une règle de décalage auto-référentielle diffère de Fibonacci pendant qu'ils changent n en direct dans le navigateur sans frais.
Questions fréquentes
Combien coûte le calculateur de la suite Q de Hofstadter ?
Il est gratuit dans votre navigateur sur cette page.
Que se passe-t-il si n est inférieur à 1 ?
La suite Q de Hofstadter n'est définie ici que pour les entiers positifs n ≥ 1.
Comment Q(n) est-il calculé ?
Les germes sont Q(1)=Q(2)=1. Pour chaque k de 3 à n le moteur pose Q(k)=Q(k−Q(k−1))+Q(k−Q(k−2)) avec un tableau d'entiers bottom-up. Le même n produit toujours le même q.
L'algorithme est-il aléatoire ?
Non. Il n'utilise que de l'arithmétique entière déterministe.
Quelles sont quelques valeurs connues ?
Q(1)=1, Q(2)=1, Q(3)=2, Q(4)=3, Q(5)=3, Q(6)=4, Q(10)=6, Q(20)=12. La suite est OEIS A005185 sous cette indexation partant de 1.
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/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)Exemple de requête
{
"n": 10
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.hofstadter_q",
"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
Cette capacité renvoie la valeur Q exacte du n-ième terme sous forme de JSON déterministe—sans solveur symbolique, sans approximation flottante, sans appel réseau—afin que correcteurs de devoirs, recoupements OEIS, validateurs de concours et démonstrations pédagogiques voient le même entier pur dans l'exécuteur gratuit du navigateur et sur la voie API prépayée à $0.002 par requête réussie.
Qu'est-ce que la suite Q de Hofstadter et comment la récurrence fonctionne
Les indices négatifs et zéro sont hors de cette définition classique : le gestionnaire rejette tout n inférieur à un avec invalid_input plutôt que d'inventer une extension signée. Lorsque vous n'avez besoin que d'un seul terme, envoyez l'indice n ; la réponse répète n, la valeur q égale à Q de n, une courte chaîne de formule et un résumé de la récurrence qui documente les germes et la règle afin que correcteurs et élèves puissent recalculer à la main de petits cas et confronter l'API ligne par ligne sans ambiguïté sur la convention d'indexation.
Comment appeler l'API et ce que contient la réponse
Une réponse réussie inclut n en écho, q égal à Q de n, formula avec la chaîne Q de n égal à Q de n moins Q de n moins un plus Q de n moins Q de n moins deux, et recurrence documentant Q de un égal à Q de deux égal à un et la règle pour n supérieur à deux. Préférez des exemples de classe appariés comme n égal à un donnant un, n égal à dix donnant six, n égal à vingt donnant douze, et un n nul ou négatif illustrant le rejet strict. Envoyez un corps JSON avec un unique champ obligatoire n : un entier positif d'au moins un et d'au plus cent mille, l'indice partant de un du terme Q souhaité. Les alias index, order et term sont acceptés avec le même sens afin que formulaires, tableurs et chaînes de requête réutilisent un seul contrat. Une validation échouée—n manquant, non entier, fraction, notation scientifique, valeur au-dessus de la limite publiée ou tout n inférieur à un—renvoie invalid_input et n'est jamais facturée. Le tarif est un forfait de $0.002 par requête réussie avec unité item.
Conseils pratiques, limites et place de la suite Q
Sur cette page le travail s'exécute entièrement dans votre navigateur ; via l'API chaque consultation réussie coûte $0.002, une validation échouée n'est pas facturée et rien n'est stocké après la réponse. Limitez n à cent mille pour borner mémoire et temps Worker ; Q de n croît approximativement comme n sur deux et reste un entier sûr dans cette plage. Associez cette page à Fibonacci, Padovan, Collatz et d'autres outils de suites lorsque vous construisez un petit laboratoire récréatif de théorie des nombres d'endpoints gratuits et déterministes.
Cas d'intégration
Fixtures de tests déterministes
Générez des valeurs Q reproductibles pour tests unitaires, contrôles de propriétés et assertions CI fixant indices connus et termes attendus.