2硬貨のフロベニウス数
4と7の硬貨なら17より大きい金額はすべて支払えますが、17だけは作れません。互いに素な2つの値について、この支払えない最大の金額と、作れない金額の個数を求めます。切手の問題や数学コンテストの準備に役立ちます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- A
- 4
- B
- 7
- Gcd
- 1
- フロベニウス数
- 17
- 表現不可能な数の個数
- 9
互いに素な2つの正の整数のフロベニウス数とは、それらの非負整数の組み合わせとして書けない最大の整数です。2硬貨問題では、額面aとbのgcdが1のとき、ぴったり作れる金額と作れない金額があり、フロベニウス数は作れない最大の金額です。この計算機は2つの正の整数を受け取り、互いに素であることを確認し、2種の額面に対する閉じた答えであるab引くa引くbを返します。切手パズル、Chicken McNugget風の問題、コンテスト対策、数値半群の授業に、計算機代数システムを立てずにご利用ください。
2硬貨のフロベニウス数とは何か、公式はどう働くか
2硬貨のフロベニウス問題は、xとyが非負整数でaとbが互いに素な正の整数であるとき、axたすbyとして表せない最大の整数を求めます。aとbのgcdが1のとき、十分に大きい整数はすべて表せ、最大の例外がはっきり定義されます。Sylvesterは、この例外がaかけるb引くa引くbに等しいことを示しました。
たとえば額面4と7は17になります。4と7では17より大きい整数はすべて作れますが、17自身は作れません。額面3と5は7です。 額面2といかなる奇数nもn引く2です。
表せない正の整数の個数は、a引く1かけるb引く1を2で割った値で、4と7ではその個数は9です。一方の額面が1なら、すべての非負整数が表せ、公式は−1を返し、表せない個数は0です。1単位の硬貨でパズルが自明になっても、これは数学的に一貫しています。
能力は解析済みの対、そのgcd（成功時は常に1）、coprimeフラグ、フロベニウス数、表せない個数、公式文字列ab引くa引くbを返し、答えの横に恒等式を示せます。
入力契約、互いに素の判定、エラー時の振る舞い
十進文字列、および第1値の別名xまたはm、第2値の別名yまたはnも受け付けるため、表計算、クエリ文字列、授業用フォームが1つの契約を再利用できます。解析の後、エンジンはユークリッドのgcdを計算します。そのgcdがちょうど1でなければ、gcdで割り切れない整数は永遠に到達不能なためフロベニウス数は未定義であり、作れない最大額は存在しません。
ハンドラはその対を、aとbが互いに素でなければならないという明確なメッセージで拒否します。古典的な落とし穴は6と9、4と6、10と15です。有効な互いに素な対では、積aかけるbが安全な整数範囲内で作られ、フロベニウス数はab引くa引くb、表せない個数はちょうど(a引く1)かける(b引く1)を2で割った整数です。
近い整数を誤答へずらす浮動小数点の段はありません。検証失敗は課金されません。
2硬貨フロベニウス計算機が役立つ場面
教員はフロベニウス数の計算機を使い、生徒が2硬貨の切手問題やChicken McNugget風の問題を、ab引くa引くbの符号を取り違えずに確認できるようにします。コンテスト指導者は、公約数があるときに意味を失う公式を返すのではなく、互いに素でない対を拒否する決定的なオラクルを必要とします。
数値半群のノートや整数計画のデモは、しばしば2つの生成元から始め、生成元を増やす前にフロベニウス数より1大きい導手を求めます。gcdの判定だけが必要なときは互いに素チェッカーと、作れない最大額ではなくBézout係数が必要なときは拡張ユークリッドの道具と組み合わせてください。
活用例
切手と2硬貨のパズル
互いに素な2つの切手額面ではちょうど作れない最大の郵便料金、または2つの硬貨額面では届かない最大の会計合計を求めます。
授業とコンテストの解答キー
互いに素でない対を拒否し、有効な生成元にはab引くa引くbを返す決定的オラクルで、Chicken McNugget風の設問を採点します。
数値半群のノート
第3の生成元を足したり導手を計算したりする前に、フロベニウス数と表せない個数で2生成元の半群を初期化します。
よくある質問
互いに素な2整数のフロベニウス数とは何ですか？
非負整数xとyによるax + byとして書けない最大の整数です。互いに素なaとbでは値はab − a − bです。
なぜaとbは互いに素でなければなりませんか？
gcd(a,b)が1より大きいと、そのgcdで割り切れない整数はすべて到達不能なので、作れない最大額は存在しません。
一方の額面が1のときはどうなりますか？
すべての非負整数が表せます。公式は−1を返し、表せない個数は0です。これは一貫した閉じた結果です。
3つの箱サイズのChicken McNugget問題も解けますか？
いいえ。 このページは2硬貨（2生成元）の場合のみです。3種以上の額面には同程度に簡単な閉形式がなく、対象外です。
2種類の硬貨で作れない金額はいくつありますか？
それぞれの値から1を引いて掛け合わせ、2で割った (a − 1)(b − 1)/2 個です。4と7の硬貨なら作れない金額は9個で、そのうち最大は17です。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/frobenius-number \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":4,"b":7}'const res = await fetch("https://api.kit.forhosting.com/numth/frobenius-number", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 4,
"b": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/frobenius-number",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 4,
"b": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/frobenius-number", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":4,"b":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":4,"b":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/frobenius-number", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"a": 4,
"b": 7
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.frobenius_number",
"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 | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
対が1より大きい公約数を共有する場合、無限個の剰余が到達不能のまま残るため、作れない最大額は存在せず、数を捏造する代わりにinvalid_inputで失敗します。
入力契約、互いに素の判定、エラー時の振る舞い
必須の正の整数aとbを含むJSON本体を送ってください。各値は1から1000万までの整数でなければならず、分数、指数表記、先頭のごみ、0、負数、範囲外の値はフィールド名付きのinvalid_inputで失敗します。欠落フィールド、空文字列、非数値型は算術の前に失敗します。
2硬貨フロベニウス計算機が役立つ場面
実装は純粋なparseのティアAであるため、成功した呼び出しは公開された基本料金$0.002で、モデルトークンも外向き通信もありません。リクエストを文書化された範囲に収め、テストで数値フィールドを固定すれば、数論のどの授業でもいずれ黒板に書く2行の恒等式のために計算機代数を立てなくても、宿題、LMSプラグイン、エッジワーカー向けに再現可能な答えが得られます。
技術的な質問
フロベニウス数の計算機の料金はいくらですか？
ブラウザの道具は無料です。APIリクエストは成功した呼び出しごとに前払いのKIT残高から$0.002です。無効な入力は課金されません。