ピサノ周期計算機
1,000,000までの法でピサノ周期を求めます。法10ではフィボナッチ数の余りが60ステップごとに、法2では3ステップごとに繰り返されます。結果は整数だけで計算した正確な周期の長さです。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- M
- 10
- ピサノ周期
- 60
ピサノ周期計算機は、指定した正の法に対してフィボナッチ剰余列が繰り返し始めるまでに現れる剰余の数を求めます。任意の個数のフィボナッチ項を生成するのではなく、連続する剰余の組を追跡し、唯一の初期状態に戻った時点で周期の長さを返します。剰余算、競技プログラミング、漸化式の解析、非常に大きなフィボナッチ添字を安全に縮約するアルゴリズムに役立ちます。1から1,000,000までの法を入力すると、正確で決定的な結果を取得できます。
ピサノ周期が表すもの
フィボナッチ数列は0, 1, 1, 2, 3, 5から始まり、直前の2項を加えて続きます。各項をmで割った余りに置き換えると、フィボナッチ数を法mで見た剰余列になります。順序付きの剰余の組は有限個しかないため、この新しい列は最終的に繰り返します。
フィボナッチ剰余列では反復が最初の組へ戻り、その復帰までのステップ数をピサノ周期と呼びます。たとえば法2では剰余が0, 1, 1となった後に同じパターンが再開するため、周期は3です。法10の周期は60であり、フィボナッチ数の末尾の数字が60項ごとに繰り返す理由もここにあります。
この計算機が返すのは周期の長さであり、剰余の一覧や特定のフィボナッチ項ではありません。特別な法1では剰余が0しかないため、1状態の列の周期は1です。対応するすべての計算は正確な整数演算で行い、近似、標本抽出、確率的検定は使用しません。
計算機が周期を検出する仕組み
フィボナッチの値は直前の2つの値に依存するため、1つの剰余が再び現れただけでは数列全体が再開したとは証明できません。そのため、この計算機は連続する剰余の順序付きの組を追跡します。0と1から開始し、その組を次のフィボナッチ剰余の組へ順次更新しながら、各遷移を数えます。
順序付きの組0, 1が再び現れたとき、その回数がピサノ周期です。組を用いる検査により、0だけ、または任意の単一剰余の反復だけを監視した場合に起こり得る誤停止を防ぎます。計算に必要なのは現在の組とカウンターだけで、周期全体を保存しないため、メモリ使用量は一定です。
入力は正の整数でなければなりません。小数、数値でない文字列、0、負数、公開上限を超える値は、丸めたり暗黙に変更したりせず拒否します。
フィボナッチの剰余計算で結果を使う方法
周期pが分かれば、法mでの値だけが必要な場合にフィボナッチ添字を法pで縮約できます。すなわち、F(n) mod mはF(n mod p) mod mと等しくなります。この恒等式により、高速倍加法や行列累乗を実行する前に、巨大な添字をはるかに小さい同値な添字へ変換できます。
添字が非常に長い10進文字列で与えられる場合、暗号学の演習に漸化式が現れる場合、またはプログラミング問題で末尾の数字だけが求められる場合に特に有用です。2つの法の役割は区別してください。mはフィボナッチ剰余を決め、返されたピサノ周期は添字の縮約に使います。
一般に周期はmと同じではなく、合成数を法とする周期には素数冪因子の相互作用が反映されます。項ごとの追加料金はなく、アルゴリズムはネットワークや外部データを利用しません。
活用例
巨大なフィボナッチ添字を縮約する
最初に周期の長さを求め、その周期で添字を縮約して、同値なフィボナッチ剰余位置だけを計算します。
末尾の数字の反復を確認する
法10、100、または別の10の冪を用いて、フィボナッチ数の末尾の数字が繰り返す間隔を調べます。
整数論の演習を検証する
漸化式、合同式、素数冪、合成数の法を学ぶ際に、予想した剰余周期の長さを確認します。
よくある質問
ピサノ周期とは何ですか？
法mのフィボナッチ剰余列が初期状態へ戻って反復するまでに現れる剰余の数です。
法1のピサノ周期が1なのはなぜですか？
法1ではすべての整数の剰余が0となるため、剰余列は1つの状態だけを繰り返します。
結果はフィボナッチ数そのものですか？
いいえ。 指定した法におけるフィボナッチ剰余の反復周期の長さです。
フィボナッチ数の下1桁はなぜ繰り返すのですか？
下1桁は10で割った余りであり、法10のピサノ周期は60だからです。そのため、フィボナッチ数の下1桁は60項ごとに同じ並びに戻ります。
大きな番号のフィボナッチ数にピサノ周期はどう役立ちますか？
法mでの余りだけが必要なら、先に番号を小さくできます。周期をpとすると、F(n) mod m は F(n mod p) mod m と等しくなります。法10なら番号を60で割った余りだけで足ります。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/pisano-period \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"m":10}'const res = await fetch("https://api.kit.forhosting.com/numth/pisano-period", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"m": 10
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pisano-period",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"m": 10
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pisano-period", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"m":10}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"m":10}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pisano-period", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"m": 10
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pisano_period",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_m | 1000000 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
計算機が周期を検出する仕組み
対話的なリクエストの実行時間を明確に制限するため、法の上限は1,000,000です。ブラウザーとAPIでは同じ決定的な中核処理を使用します。
フィボナッチの剰余計算で結果を使う方法
再現可能な処理のため、入力したmと返されたpisano_periodの両方を保存してください。この理由から応答には両フィールドが含まれます。1回のリクエスト料金は$0.002です。
技術的な質問
0または負の法を入力できますか？
いいえ。1未満の法は無効であり、invalid_inputエラーが返されます。
対応する法の最大値はいくつですか？
各リクエストの実行上限を明確に保つため、1から1,000,000までの正の整数に対応します。
APIリクエストの料金はいくらですか？
各リクエストの料金は$0.002です。項数に応じた変動料金はありません。