ForHosting KIT · 数学

Calkin–Wilf第n項

Calkin-Wilf列の5番目の項は3/2で、根1/1から左に1歩、右に1歩進んだところにあります。1から10億までの位置を入力すると、既約分数とその道筋が分かります。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

N: 5

結果

分子: 3
分母: 2
分数: 3/2
パス: LR

Calkin–Wilf木は、正の有理数をちょうど一度ずつ既約形で並べた完全二分木です。木をレベル順に読む（または正の整数nの二進経路と一致する自然なヒープ順で節を番号付ける）と、Q+の有名な列挙であるCalkin–Wilf列が得られます。添字1は根の分数1/1であり、それ以降の添字は、先頭の1ビットを除いたnの二進桁が符号化する一意の左右経路に従います。列挙組合せ、離散数学、有理数再構成を学ぶ方には、木全体を構築せず任意の安全な添字の分子と分母を返す高速なオラクルが必要です。本機能は正の整数nを受け取り、少数の整数加算でその経路をたどり、既約分数a/bと経路文字列および短い公式を返します。

Calkin–Wilf列挙とは何か、第n分数の定義

Neil CalkinとHerbert Wilfは、正の有理数のきわめて単純な二分木を広めました。根は1/1、分数a/bの左の子はa/(a+b)、右の子は(a+b)/bです。すべての正の有理数が既約形でちょうど一度現れ、木はQ+の列挙であると同時に各値の標準既約形でもあります。

1始まりの自然な添字nは完全二分ヒープ順での位置で節をラベルします。nが1なら根、2なら根の左の子（1/2）、3なら右の子（2/1）、4なら左左の孫（1/3）という具合です。同等に、nを二進で書き、常に根を示す先頭の1ビットを落とし、残りの各ビットを上位から下位へ動きとして解釈します。

0は左、1は右です。これらの動きの後、その節の一意の既約分数a/bが得られます。古典的な恒等式はこの歩行をSternの二原子数列sに結びます。添字nのCalkin–Wilf分数はs(n)/s(n+1)です。

各ステップは正の整数二つを加えるだけなので、アルゴリズムは決定的で割当が軽く、浮動小数の丸めがありません。宿題のオラクル、LMSプラグイン、近似小数ではなく厳密な分子・分母を要する研究ノートに適しています。

入力内容と結果の見方

0を含む1未満の値とすべての負の添字は、Calkin–Wilf添字が少なくとも1である旨の明確なメッセージで失敗し、その検証失敗は課金されません。

成功時はnをエコーし、正の整数のnumeratorとdenominator、表示用文字列のfraction（分子/分母）、根と子の規則および二進経路規則の短い再述formula、根以降の移動を示すLとRのpath（nが1のときは単語root）を返します。例：nが1なら分数1/1、pathはroot。

例：nが5なら二進101、経路ビットは0次いで1なので1/1から左→右で3/2、pathはLR。例：nが7ならpathはRR、分数は3/1。有理数だけが必要なクライアントはfractionまたは整数対を読めます。

指導者は答えの横にpathを示し、学習者が各左右ステップを監査できます。実装は純粋parseのティアAで、ネットワークもモデルトークンもファイルシステムもなく、同じモジュールが無料ブラウザ経路とエッジWorkerで結果をずらさず動作します。

活用例

教室と宿題の確認

学習者に正の添字nを提出させ、左右の子規則に照らしてCalkin–Wilf分数a/bを検証し、部分点のために経路文字列を表示します。

LMSと試験の自動採点

1未満のnを拒否し、非既約や重複の有理数を決して捏造しない決定的オラクルでCalkin–Wilf列挙問題を採点します。

一意な正のテスト有理数

乱数対にgcdを呼ばず、性質ベーステスト用に添字ごとの相異なる既約正有理数の列を生成します。

よくある質問

nが0または負の場合はどうなりますか？

ここで用いるCalkin–Wilf添字は1始まりの正の整数であり、1未満は拒否され課金されません。

返される分数は常に既約ですか？

はい。 Calkin–Wilf木の各節はすでに既約なので、有効なすべてのnでnumeratorとdenominatorは互いに素です。

Stern–Brocot列との違いは何ですか？

Sternの二原子数列は単一の整数s(n)を返します。Calkin–Wilf項は有理数s(n)/s(n+1)（上記の木歩行と同等）です。検索意図と出力形状は分数対二原子値で異なります。

LとRの道筋は何を意味しますか？

nを2進数で書いて先頭の1を除き、残った0は左へ、1は右へ根から進む一歩を表します。5なら2進数101から0と1が残るので、道筋はLRで3/2に着きます。

すべての正の分数が列に現れますか？

はい、どの正の分数もちょうど一度、しかも既約の形で現れます。そのため、2/4と1/2のような重複のない、正の有理数の完全な一覧になります。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/numth/calkin-wilf-term

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/numth/calkin-wilf-term \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":5}'

const res = await fetch("https://api.kit.forhosting.com/numth/calkin-wilf-term", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": 5
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/calkin-wilf-term",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 5
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/calkin-wilf-term", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":5}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":5}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/calkin-wilf-term", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": 5
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.calkin_wilf_term",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

1未満の添字はinvalid_inputで拒否され、採点器やスクリプトが0や負の位置を有効な項と誤認しません。

Calkin–Wilf列挙とは何か、第n分数の定義

本エンドポイントは別のStern表ではなく直接の木歩行を実装しますが、すべての正のnでその恒等式と一致します。

入力契約、応答フィールド、エラー動作

必須フィールドnだけを含むJSON本体をPOSTしてください。nは1以上の正の整数で、JSON数値または十進数字列、最大10億です。別名indexとorderも同じ意味で受け付けます。n欠落、空文字、非整数、非有限数、上限超過は問題を示すinvalid_inputで失敗します。

Calkin–Wilf項APIが役立つ場面

列挙組合せと離散数学の授業は、正の整数と正の有理数の全単射、連分数との関係、Stern–Brocot木との比較を教える際にCalkin–Wilf木を使います。超二進表現、Minkowskiの疑問符関数のデモ、有理サンプリング戦略を探る研究ノートは、構成上既約なまま第nのCalkin–Wilf分数の厳密で速いオラクルをしばしば必要とします。性質ベーステスト用に一意な正のテスト有理数を生成する工学・教育ツールは、後でgcd整理が必要な乱雑な非既約対を作る代わりに、添字で連続項を取得できます。小さなAPIにより、LMSプラグインは完全な数式処理系を配布せず任意のnの解答を照合できます。成功した各呼び出しはモデルトークンも外向き通信もなく公開の基本価格$0.002で、検証失敗は残高を消費せず、アルゴリズムはO(log n)の整数加算のみなので、重い数論基盤なしに宿題・採点・エッジWorker向けの再現可能な分数が得られます。リクエストは小さく保ち、nが1始まりの正の整数であることを文書化し、自動検査ではnumerator・denominator・fractionを正規の回答フィールドとして扱ってください。

技術的な質問

第nのCalkin–Wilf分数をどう取得しますか？

正の整数n（n ≥ 1）を送ってください。APIはCalkin–Wilf木でnの二進経路が到達する節のnumerator・denominator・fraction a/bを返します（根は1/1）。

Calkin–Wilf項計算機の料金は？

ブラウザツールは無料です。API要求は成功した呼び出しごとに前払いKIT残高から$0.002です。無効入力は課金されません。

KITの完全なドキュメントを見る →

Calkin–Wilf第n項

無料で実行

計算例

Calkin–Wilf列挙とは何か、第n分数の定義

入力内容と結果の見方

活用例

教室と宿題の確認

LMSと試験の自動採点

一意な正のテスト有理数

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

エラー

技術的な注記

Calkin–Wilf列挙とは何か、第n分数の定義

入力契約、応答フィールド、エラー動作

Calkin–Wilf項APIが役立つ場面

技術的な質問

ありがとう