时间戳

首页 > 解决方案 > 给定 n 的总函数的所有实际值的总和

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

问题描述

对于给定的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。
如果有更好的解决方案？

标签： mathgreatest-common-divisor

解决方案

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

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

在oeis中查找函数，您会发现A023896：“n 的总和，即不超过 n 且互质为 n 的整数之和”。我们得到一个公式：
n*phi(n)/2除了n=1. 这phi是欧拉的总函数，欧拉本人对此表示了快速计算：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 等）。

如果您需要计算大量数字的质因数，您可以构建一个 Eratosthenes 筛子并将结果保存在列表中。这样，您只需要逐步遍历实际素数即可找到素数。

推荐阅读