totativesの和

正の整数 n の totatives とは、1 から n までの範囲のうち n と共通の素因数を持たない剰余のことです。その個数はオイラーのトーシェント φ(n) であり、その和は分数の列挙、円分恒等式、剰余群の演習に現れる関連した算術不変量です。本計算機は正の整数 n を一つ受け取り、決定的に素因数分解し、素数積公式から φ(n) を評価し、totatives の厳密な和を返します。n が 1 より大きいときは古典的な閉形式 n 倍の φ(n) の半分を用い、n が 1 のときは特別値 1 を用います。入力と整数の答えのあいだにネットワーク呼び出しも浮動小数の当て推量も言語モデルも挟みません。

totatives の和が測るもの

二つの正の整数は最大公約数が 1 のとき互いに素です。n の totatives の集合は、1 以上 n 以下で gcd(k, n) が 1 である整数 k の集合そのものです。オイラーのトーシェント φ(n) はその集合の個数を数え、totatives の和はその元を足し合わせます。

素数 p では totatives は 1 から p 引く 1 までなので、和は (p 引く 1) かける p を 2 で割った値となり、これは p かける φ(p) を 2 で割った値と一致します。合成数 n でも n が 1 より大きいときは同じペアリングが成り立ちます。

k が n と互いに素なら n 引く k もそうであり、両者は相異なり平均は n の半分なので、全体の和は n かける φ(n) を 2 で割った値になります。学習者は教科書の totatives 表を確認するとき、分母 n の既約分数の分子が平均 n の半分になることを確かめるとき、手作業の互いに素リストと φ(n) を見比べるときにこの和に出会います。

技術者は法の安価な不変量として個数と和の両方を必要とする数論パイプラインで使います。n・和・φ(n)・φ(n) を生んだ素因数を返す一つの決定的な能力があれば、宿題チェッカーや整数テストハーネスでの off-by-one ミスのよくある原因を除けます。

本計算機が和を評価する手順

実装はまず n が公開範囲である 1 から 1 兆までの整数であることを検証します。次に試し割りで n を素因数分解します。2 の因数を除き、平方根までの奇数候補を試し、最後に残った素数の余因子を取り込みます。

その順序付き素因数リストからオイラー積の厳密な整数形を適用します。phi を n から始め、n を割る各相異なる素数 p について phi を phi を p で割った床値に (p 引く 1) を掛けたものへ置き換えます。n が 1 のとき和は 1 と定義されます。

唯一の totative が 1 であり、半分の公式では誤って 2 分の 1 になるからです。n が 1 より大きいとき和は n に phi を掛けて 2 で割った値です。1 より大きい任意の整数 n について n と φ(n) の積は偶数なので、結果は常に余りなしの厳密な整数になります。

応答には n、sum、phi、素数と指数の対としての素因数リスト、適用した場合を記す短い formula 文字列が含まれます。

実用・制限・料金・提供形態

学習中、数論の演習採点、互いに素の手作業列挙の突合せで、すぐに totatives の和が欲しいときはブラウザツールをご利用ください。検証失敗は残高を消費しません。受理範囲は 1 から 1 兆までの整数で、中間積を JavaScript の安全整数範囲に保ちつつ、競技・教室・応用の典型サイズをカバーします。

結果は完全に決定的で、同じ n は常に同じ sum・同じ phi・同じ素因数リストを返します。言語モデルも外部因数分解サービスも乱数もないため、自動テストに固定しても安全です。