ホフスタッターQ数列
ホフスタッターQ数列の第10項は6、第20項は12です。新しい項は、前の項が決める距離だけさかのぼって値を足すため、増え方が不規則になります。10万までの任意の項を求められます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- N
- 10
- Q
- 6
- 漸化式
- Q(1)=Q(2)=1; Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) for n>2
ホフスタッターのQ数列は『ゲーデル、エッシャー、バッハ』で知られるメタ・フィボナッチ型の有名な漸化式です。各項は既に求めた項をオフセットとして参照し、さらに前の項を引き出します。種子はQの1とQの2がともに1であり、それより大きい添字ではQのnはQのnからQのnマイナス1を引いた位置の値に、QのnからQのnマイナス2を引いた位置の値を加えたものです。数列は1、1、2、3、3、4、5、5、6、6から始まり、平均的にはおよそnの半分付近で不規則に増えます。
ホフスタッターのQ数列とは何か、漸化式の仕組み
ダグラス・ホフスタッターは、再帰呼び出しの引数が固定ラグではなく既に計算した値に依存する、フィボナッチの混沌とした親戚としてQ数列を導入しました。古典的な種子はQの1が1、Qの2が1です。2より大きい整数nでは、定義はQのnがQのnマイナスQのnマイナス1、プラスQのnマイナスQのnマイナス2です。
最初の数段を展開すると2、3、3、4、5、5、6、6、6、8、8、8、10などになります。常に直前の2項を足すフィボナッチと異なり、Qはそれらの直前項を数列自身へのオフセットとして使うため、成長は単純な閉形式では単調ではなく、項は線形トレンドの周りで揺らぎます。ここで用いる1始まりの添字では、数列はOEIS A005185として登録されています。
負の添字と0はこの古典定義の外です。1項だけが必要なときは添字nを送ってください。
実用上の注意、上限、Q数列の位置づけ
学習者は定数係数の線形漸化式ではない再帰定義を学ぶとき、メタ・フィボナッチ族を比較するとき、単純な自己参照規則が局所的に不規則でもすべての正整数で定義される様子を探るときに、ホフスタッターのQ数列に出会います。教員は種子を隠す不透明な電卓に頼らず、与えられたnのQを求めるプリントの解答キーを作れます。
開発者は同じ契約で数論ライブラリのサンプル検証、プロパティテストの種、デモ前の期待項の事前計算に使えます。コンテスト練習では時間制約下でOEIS表を落とさずに済む、オフラインで速いQ値源がしばしば必要です。メモリとWorker時間を抑えるためnは10万までとし、Qのnはおおよそnの半分程度で増え、その範囲では安全整数に収まります。
一部のコード例にある0始まりの表シフトと、1始まりのQの1が1である規約を混同しないでください。別規約で採点する前に、必ずrecurrence欄の種子を確認してください。
活用例
宿題・コンテストでのQ(n)照合
長い手計算の漸化式表やその場しのぎのスクリプトなしに、プリントやコンテスト検証用にホフスタッターQのnを計算します。
決定論的なテスト用フィクスチャ
既知の添字と期待項を固定した単体テスト、プロパティ検査、CIアサーション用に再現可能なQ値を生成します。
メタ・フィボナッチ漸化式の授業
自己参照オフセット規則がフィボナッチとどう違うかを、学習者がブラウザでnを無料で変えながら示します。
よくある質問
nが1未満のときはどうなりますか？
ここでのホフスタッターQ数列は正整数n ≥ 1にのみ定義されます。
Q(n)はどう計算されますか？
種子はQ(1)=Q(2)=1です。エンジンはkを3からnまで進め、ボトムアップ整数配列でQ(k)=Q(k−Q(k−1))+Q(k−Q(k−2))と置きます。同じnは常に同じqを返します。
既知の値にはどのようなものがありますか？
Q(1)=1、Q(2)=1、Q(3)=2、Q(4)=3、Q(5)=3、Q(6)=4、Q(10)=6、Q(20)=12です。この1始まり添字では数列はOEIS A005185です。
Q数列はフィボナッチ数列とどう違いますか？
フィボナッチ数列は直前の2項を足します。Q数列はその2項を「さかのぼる距離」として使い、そこにある項を足します。そのため増え方が不規則で、平均すると n/2 付近になります。
添字はいくつまで入力できますか？
1から10万までです。最初の2項はどちらも1で、OEIS A005185 と同じく1から数えます。0番目から数える資料とは位置が1つずれます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
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)リクエスト例
{
"n": 10
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.hofstadter_q",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
本機能は第n項のQ値を決定論的なJSONとして返し、数式ソルバも浮動小数の推測もネットワーク呼び出しも使いません。宿題の採点、OEISとの突合、コンテスト検証、授業デモのいずれでも、無料のブラウザ実行と前払いAPI経路の$0.002／成功リクエストで同じ純整数結果が得られます。
ホフスタッターのQ数列とは何か、漸化式の仕組み
ハンドラは1未満のnをsigned拡張を発明せずinvalid_inputで拒否します。応答はnをエコーし、qにQのn、短いformula文字列、種子と規則を記したrecurrence要約を返し、採点者と学習者が小さな例を手計算し、添字規約の曖昧さなくAPIと行単位で照合できるようにしています。
APIの呼び出し方と応答に含まれる内容
nは1以上かつ10万以下の正の整数で、欲しいQ項の1始まりの添字です。成功応答にはエコーされたn、Qのnに等しいq、QのnがQのnマイナスQのnマイナス1にQのnマイナスQのnマイナス2を加えたものであるというformula、およびQの1とQの2が1でnが2より大きいときの規則を記したrecurrenceが含まれます。既知のQ値を断言するCIフィクスチャ、学習者の漸化式実装を検査する採点スクリプト、添字を変えながらQのnを描く対話授業に適します。教室ではnが1で1、nが10で6、nが20で12、0や負のnで硬拒否、といった対の例を推奨します。必須フィールドnだけのJSON本体を送ってください。同じ意味の別名index、order、termも受け付けるので、フォーム、表計算、クエリ文字列で契約を共有できます。n欠落、非整数、分数、指数表記、公開上限超過、1未満のnなど検証失敗はinvalid_inputを返し課金されません。料金は成功リクエストごとに固定の$0.002、単位はitemです。
実用上の注意、上限、Q数列の位置づけ
本ページでは処理はすべてブラウザ内で走り、APIでは成功照会ごとに$0.002、検証失敗は課金せず、応答後に保存もしません。無料で決定論的なエンドポイントの小さな娯楽数論ラボを組むときは、フィボナッチ、パドヴァン、コラッツなど他の数列ツールと並べてください。
技術的な質問
ホフスタッターQ数列計算機の料金は？
本ページのブラウザ実行は無料です。APIでは成功リクエストが$0.002で、無効な入力は課金されません。
アルゴリズムは乱数を使いますか？
いいえ。決定論的な整数演算のみです。ネットワークもDateもMath.randomも使いません。