Hofstadter-Q-Folge
In der Hofstadter-Q-Folge ist das zehnte Glied 6 und das zwanzigste 12. Jedes neue Glied blickt um Abstände zurück, die frühere Glieder festlegen, daher wächst die Folge unregelmäßig; hier erhalten Sie jedes Glied bis Index hunderttausend. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Rechenbeispiel
- N
- 10
- Q
- 6
- Rekursion
- Q(1)=Q(2)=1; Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) for n>2
Die Hofstadter-Q-Folge ist eine berühmte Meta-Fibonacci-Rekursion aus Gödel, Escher, Bach: jeder Term greift auf frühere Terme zu und nutzt dabei andere Terme als Versätze. Mit den Startwerten Q von eins und Q von zwei gleich eins lautet die Regel für jeden größeren Index: Q von n gleich Q von n minus Q von n minus eins, plus Q von n minus Q von n minus zwei. Die Folge beginnt mit eins, eins, zwei, drei, drei, vier, fünf, fünf, sechs, sechs und wächst unregelmäßig nahe n durch zwei im Mittel.
Was die Hofstadter-Q-Folge ist und wie die Rekursion funktioniert
Douglas Hofstadter führte die Q-Folge als chaotische Verwandte der Fibonacci-Folge ein, bei der die Argumente der rekursiven Aufrufe von bereits berechneten Werten abhängen und nicht von festen Verzögerungen. Die klassischen Startwerte sind Q von eins gleich eins und Q von zwei gleich eins. Für jede ganze Zahl n größer als zwei gilt: Q von n gleich Q von n minus Q von n minus eins, plus Q von n minus Q von n minus zwei.
Die ersten Schritte liefern zwei, drei, drei, vier, fünf, fünf, sechs, sechs, sechs, acht, acht, acht, zehn und so weiter. Im Gegensatz zu Fibonacci, das stets die beiden unmittelbaren Vorgänger addiert, nutzt Q diese Vorgänger als Versätze in die Folge selbst, sodass das Wachstum nicht monoton in einer einfachen geschlossenen Form ist und die Terme um einen linearen Trend schwanken. Die Folge ist als OEIS A005185 unter der hier verwendeten 1-basierten Indizierung katalogisiert.
Praktische Tipps, Grenzen und Einordnung der Q-Folge
Lernende begegnen der Hofstadter-Q-Folge beim Studium rekursiver Definitionen, die keine linearen Rekursionen mit konstanten Koeffizienten sind, beim Vergleich meta-Fibonacci-Familien und bei der Frage, wie eine einfache selbstbezügliche Regel unregelmäßiges lokales Verhalten erzeugen und dennoch für jede positive ganze Zahl wohldefiniert bleiben kann. Lehrkräfte können Antwortschlüssel für Arbeitsblätter erzeugen, die Q eines gegebenen n verlangen, ohne undurchsichtigen Rechner-Apps zu vertrauen, die die Startwerte verbergen. Entwickler nutzen denselben Vertrag, um Beispieldaten für zahlentheoretische Bibliotheken zu validieren, Property-Tests zu speisen oder erwartete Terme vor einer Demo vorab zu berechnen.
Wettbewerbstraining braucht oft eine schnelle Offline-Quelle für Q-Werte, damit Lösungen ohne OEIS-Download unter Zeitdruck geprüft werden können. Kombinieren Sie diese Seite mit Fibonacci, Padovan, Collatz und anderen Folgen-Tools, wenn Sie ein kleines freizeitliches Zahlentheorie-Labor freier, deterministischer Endpunkte aufbauen. Verwechseln Sie nicht das 1-basierte Q von eins gleich eins mit 0-basierten Tabellenverschiebungen mancher Codebeispiele—prüfen Sie stets die Startwerte im Feld recurrence, bevor Sie gegen eine andere Konvention bewerten.
Anwendungsfälle
Q(n)-Prüfungen für Hausaufgaben und Wettbewerbe
Berechnen Sie die Hofstadter-Q von n für Arbeitsblätter und Wettbewerbvalidatoren ohne lange manuelle Rekursionstabellen oder Ad-hoc-Skripte.
Lehre meta-Fibonacci-Rekursionen
Zeigen Sie Lernenden, wie sich eine selbstbezügliche Versatzregel von Fibonacci unterscheidet, während sie n live im Browser kostenlos ändern.
Häufige Fragen
Was kostet der Hofstadter-Q-Folge-Rechner?
Er ist auf dieser Seite in Ihrem Browser kostenlos.
Was geschieht, wenn n unter 1 liegt?
Die Hofstadter-Q-Folge ist hier nur für positive ganze Zahlen n ≥ 1 definiert.
Wie wird Q(n) berechnet?
Die Startwerte sind Q(1)=Q(2)=1. Für jedes k von 3 bis n setzt die Engine Q(k)=Q(k−Q(k−1))+Q(k−Q(k−2)) mit einem Bottom-up-Ganzzahlarray. Dasselbe n liefert stets dasselbe q.
Welche bekannten Werte gibt es?
Q(1)=1, Q(2)=1, Q(3)=2, Q(4)=3, Q(5)=3, Q(6)=4, Q(10)=6, Q(20)=12. Die Folge ist OEIS A005185 unter dieser 1-basierten Indizierung.
Worin unterscheidet sich die Q-Folge von Fibonacci?
Fibonacci addiert die beiden vorherigen Glieder. Die Q-Folge nutzt diese beiden Glieder als Abstände, um zurückzublicken, und addiert die dort gefundenen Glieder. Deshalb wächst sie unregelmäßig, im Mittel nahe n/2.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem 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)Beispiel-Anfrage
{
"n": 10
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.hofstadter_q",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Diese Fähigkeit liefert den exakten n-ten Q-Wert als deterministisches JSON—ohne symbolischen Solver, ohne Gleitkomma-Schätzung, ohne Netzaufruf—sodass Hausaufgabenprüfer, OEIS-Abgleiche, Wettbewerbvalidatoren und Lehrdemos dasselbe reine Ganzzahl-Ergebnis im kostenlosen Browser-Läufer und auf dem vorausbezahlten API-Pfad zu $0.002 pro erfolgreicher Anfrage sehen.
Was die Hofstadter-Q-Folge ist und wie die Rekursion funktioniert
Wenn Sie nur einen Term benötigen, senden Sie den Index n; die Antwort wiederholt n, den Wert q gleich Q von n, eine kurze Formelzeichenkette und eine Rekursionsübersicht, die Startwerte und Regel dokumentiert, damit Bewerter und Lernende kleine Fälle von Hand nachrechnen und die API zeilenweise abgleichen können, ohne Unklarheit über die Indizierungskonvention.
Wie Sie die API aufrufen und was die Antwort enthält
Eine erfolgreiche Antwort enthält n als Echo, q gleich Q von n, formula mit der Zeichenkette Q von n gleich Q von n minus Q von n minus eins plus Q von n minus Q von n minus zwei, und recurrence mit Q von eins gleich Q von zwei gleich eins und der Regel für n größer als zwei. Bevorzugen Sie gepaarte Unterrichtsbeispiele wie n gleich eins ergibt eins, n gleich zehn ergibt sechs, n gleich zwanzig ergibt zwölf sowie null oder negatives n für den harten Ablehnungspfad. Senden Sie einen JSON-Body mit dem einzigen Pflichtfeld n: eine positive ganze Zahl mindestens eins und höchstens einhunderttausend, der 1-basierte Index des gewünschten Q-Terms. Die Aliasse index, order und term werden mit derselben Bedeutung akzeptiert, damit Formulare, Tabellen und Abfragezeichenketten einen Vertrag teilen. Fehlgeschlagene Validierung—fehlendes n, Nicht-Ganzzahl, Bruch, wissenschaftliche Notation, Wert über dem veröffentlichten Limit oder jedes n unter eins—liefert invalid_input und wird nie berechnet. Der Preis ist pauschal $0.002 pro erfolgreicher Anfrage mit Einheit item.
Praktische Tipps, Grenzen und Einordnung der Q-Folge
Auf dieser Seite läuft die Arbeit vollständig in Ihrem Browser; über die API kostet jede erfolgreiche Abfrage $0.002, fehlgeschlagene Validierung wird nicht berechnet und nach der Antwort wird nichts gespeichert. Begrenzen Sie n auf einhunderttausend, damit Speicher und Worker-Zeit begrenzt bleiben; Q von n wächst ungefähr wie n durch zwei und bleibt in diesem Bereich eine sichere Ganzzahl.
Integrationsbeispiele
Deterministische Test-Fixtures
Erzeugen Sie reproduzierbare Q-Werte für Unit-Tests, Property-Checks und CI-Assertions mit festen Indizes und erwarteten Termen.
Technische Fragen
Ist der Algorithmus zufällig?
Nein. Es wird nur deterministische Ganzzahlarithmetik verwendet. Es gibt kein Netzwerk, kein Date und kein Math.random.