オイラーのトーシェント関数

オイラーのトーシェント関数は、以下の形で表すことができます(正確な定義は オイラーのφ関数 - Wikipedia にあります)。

\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

この式の括弧内の分母を揃えます。

\varphi(n) = n (\frac{p_1 - 1}{p_1}) (\frac{p_2 - 1}{p_2}) \cdots (\frac{p_k - 1}{p_k})

プログラムで値を得るときは、この式を元に以下のように計算していました。

import std.experimental.all;

int totient(int n) {
    int ret = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            ret = ret / p * (p - 1);
            while (n % p == 0) n /= p;
        }
    }
    if (n != 1) ret = ret / n * (n - 1);
    return ret;
}

void main() {
    writeln(iota(1, 20).map!totient);
    //=> [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18]
}

npca2013年部誌_競技プログラミングと初等整数論入門(PDF) と読むと、 この関数を次のように計算していました。

int totient2(int n) {
    int ret = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            ret -= ret / p; // ここが違う
            while (n % p == 0) n /= p;
        }
    }
    if (n != 1) ret -= ret / n; // ここが違う
    return ret;
}

こちらのほうが計算が単純になっていますね。この計算方法がどこから来るのか考えてみます。

最初の式に戻りますと、

\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

この式の最初の n(1 - \frac{1}{p_1}) を掛けると

\varphi(n) = (n - \frac{n}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

となります。最初の括弧内の項では、n から \frac{n}{p_1} を引いています。 次に最初の括弧内の項を A と置くと

\varphi(n) = A (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

となり、A を展開すると

\varphi(n) = (A - \frac{A}{p_2}) \cdots (1 - \frac{1}{p_k})

となります。ここで行っているのは、A から \frac{A}{p_2} を引いています。
つまり、これは ret -= ret / p がやっていることなのですね。

参考