给定 n 的 totient 函数的所有实际值的总和

Question

对于给定的 n，我如何有效地找到一个 totient 函数的所有实际值的总和。例如。 tot(10) 是 1,3,7,9 => 1+3+7+9 = 20。我尝试了下面的蛮力方法

int sum = 0;
for(int i=1;i<n;i++)
{
    if(gcd(i,n)==1)sum += i;
}
print(sum)

这是 O(nxlog(n))。其中 log(n) 用于每一步的 gcd 计算。
约束：1<=n<=10^6。
有没有更好的解决办法？

Answer 1

如果打印出函数的第一个值，您将得到：

1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, ...

正在查找 oeis, you find A023896 中的函数："Sum of totatives of n, i.e., sum of integers up to n and coprime to n"。然后我们得到一个公式：
n*phi(n)/2 除了 n=1。这里phi是欧拉的totient function，为此欧拉自己指出了一个快速计算：n * Product_{distinct primes p dividing n} (1 - 1/p).

将所有内容组合成一些纯 Python 函数：

import math

def prime_factors(n):
    if n == 1:
        return []
    if n % 2 == 0:
        return [2] + prime_factors(n//2)
    if n % 3 == 0:
        return [3] + prime_factors(n//3)
    if n % 5 == 0:
        return [5] + prime_factors(n//5)
    for i in range(6, int(math.sqrt(n)) + 1, 6):
        if n % (i + 1) == 0:
            return [i + 1] + prime_factors(n // (i + 1))
        if n % (i + 5) == 0:
            return [i + 5] + prime_factors(n // (i + 5))
    return [n]

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b)

def totative_sum(n):
    s = 0
    for i in range(1, n+1):
        if gcd(n, i) == 1:
            s += i
    return s

def phi(n):
    prod = n
    for i in set(prime_factors(n)): # convert to a set, because we don't want duplicates
        # prod = prod * (1 - 1 / i)
        prod = prod * (i - 1) // i  # rewrite the formula to only work with integers
    return int(prod)

def fast_totative_sum(n):
    if n == 1:
        return 1
    return n * phi(n) // 2

print([totative_sum(n) for n in range(1, 31)])
print([fast_totative_sum(n) for n in range(1, 31)])

n = 12345678
print(fast_totative_sum(n))
print(totative_sum(n))

输出：

[1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, 54, 171, 80, 126, 110, 253, 96, 250, 156, 243, 168, 406, 120]
24860442405888

请注意，这里的质因数分解仅遍历 6k+1 和 6k+5 的可能因数。这可以进一步优化，步进模 30，其中只需要测试 8 个因素，可以跳过 22 个。（依此类推，模210=2*3*5*7等）。

如果您需要计算大量数字的质因数，您可以构建埃拉托色尼筛法并将结果保存在列表中。这样你只需要遍历实素数就可以找到素因数。

给定 n 的 totient 函数的所有实际值的总和

sum of all actual values of a totient function for given n

math

greatest-common-divisor