Hofstadter Q sequence
In Hofstadter’s Q sequence the 10th term is 6 and the 20th is 12. Each new term looks back by distances that earlier terms decide, which makes the growth irregular; this calculator returns any term up to index one hundred thousand. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 10
- Q
- 6
- Recurrence
- Q(1)=Q(2)=1; Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) for n>2
Hofstadter's Q-sequence is a famous meta-Fibonacci recurrence from Gödel, Escher, Bach: each term looks up earlier terms using earlier terms as offsets. With seeds Q of one and Q of two equal to one, the rule for every larger index is Q of n equals Q of n minus Q of n minus one, plus Q of n minus Q of n minus two. The sequence begins one, one, two, three, three, four, five, five, six, six, and grows irregularly near n over two on average.
What Hofstadter's Q-sequence is and how the recurrence works
Douglas Hofstadter introduced the Q-sequence as a chaotic cousin of Fibonacci in which the arguments of the recursive calls depend on previously computed values rather than on fixed lags. The classical seeds are Q of one equals one and Q of two equals one. For every integer n greater than two, the definition is Q of n equals Q of n minus Q of n minus one, plus Q of n minus Q of n minus two.
Unrolling the first few steps produces two, three, three, four, five, five, six, six, six, eight, eight, eight, ten, and so on. Unlike Fibonacci, which always adds the two immediate predecessors, Q uses those predecessors as offsets into the sequence itself, so the growth is not monotone in a simple closed form and the terms fluctuate around a linear trend. The sequence is catalogued as OEIS A005185 under the one-based indexing used here.
Practical tips, limits, and where Q-sequence fits
Students meet Hofstadter's Q-sequence when studying recursive definitions that are not linear recurrences with constant coefficients, when comparing meta-Fibonacci families, and when exploring how a simple self-referential rule can produce irregular local behavior while still remaining well-defined for every positive integer. Teachers can generate answer keys for worksheets that ask for Q of a given n without trusting opaque calculator apps that hide the seeds. Developers use the same contract to validate sample data for number-theory libraries, to seed property tests, or to pre-compute expected terms before a demonstration.
Contest practice often needs a fast offline source of Q values so solutions can be checked without downloading OEIS tables under time pressure. Do not confuse one-based Q of one equals one with zero-based table shifts used in some code samples—always check the seeds printed in the recurrence field before grading against a different convention.
What you can do with it
Homework and contest Q(n) checks
Compute Hofstadter Q of n for worksheets and contest validators without manual long recurrence tables or ad-hoc scripts.
Teaching meta-Fibonacci recurrences
Show students how a self-referential offset rule differs from Fibonacci while they change n live in the browser at no cost.
FAQ
What does the Hofstadter Q sequence calculator cost?
It is free in your browser on this page.
What happens if n is below 1?
Hofstadter's Q-sequence is defined here only for positive integers n ≥ 1.
How is Q(n) computed?
Seeds are Q(1)=Q(2)=1. For each k from 3 to n the engine sets Q(k)=Q(k−Q(k−1))+Q(k−Q(k−2)) using a bottom-up integer array. The same n always yields the same q.
What are some known values?
Q(1)=1, Q(2)=1, Q(3)=2, Q(4)=3, Q(5)=3, Q(6)=4, Q(10)=6, Q(20)=12. The sequence is OEIS A005185 under this 1-based indexing.
How is the Q sequence different from Fibonacci?
Fibonacci adds the two previous terms. The Q sequence uses those two previous terms as distances to look back, then adds the terms it finds there. That is why it grows irregularly, on average near n/2, instead of smoothly.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your 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)Example request
{
"n": 10
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.hofstadter_q",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
What Hofstadter's Q-sequence is and how the recurrence works
When you only need a single term, send the index n; the response echoes n, the value q equal to Q of n, a short formula string, and a recurrence summary that documents the seeds and the rule so graders and students can recompute small cases by hand and match the API line by line without ambiguity about indexing conventions.
How to call the API and what the response contains
A successful response includes n as echoed, q equal to Q of n, formula equal to the string Q of n equals Q of n minus Q of n minus one plus Q of n minus Q of n minus two, and recurrence documenting Q of one equals Q of two equals one and the rule for n greater than two. Prefer paired classroom examples such as n equals one yielding one, n equals ten yielding six, n equals twenty yielding twelve, and a zero or negative n demonstrating the hard rejection path. Send a JSON body with a single required field n: a positive whole number at least one and at most one hundred thousand, the one-based index of the Q term you want. Aliases index, order, and term are accepted for the same meaning so forms, spreadsheets, and query strings can reuse one contract. Failed validation—a missing n, a non-integer, a fraction, scientific notation, a value above the published limit, or any n below one—returns invalid_input and is never charged. Pricing is a flat $0.002 per successful request with unit item.
Practical tips, limits, and where Q-sequence fits
On this page the work runs entirely in your browser; through the API each successful lookup costs $0.002, failed validation is not charged, and nothing is stored after the response returns. Cap n at one hundred thousand so memory and Worker time stay bounded; Q of n itself grows roughly like n over two and remains a safe integer throughout that range. Pair this landing with Fibonacci, Padovan, Collatz, and other sequence tools when you are building a small recreational number-theory lab of free, deterministic endpoints.
Integration use cases
Deterministic test fixtures
Generate reproducible Q values for unit tests, property checks, and CI assertions that fix known indices and expected terms.
Technical questions
Is the algorithm randomized?
No. It uses deterministic integer arithmetic only. There is no network, no Date, and no Math.random.