algorithm - 从1到N的欧拉Totient函数的有效求和

Question

问题总结

当H定义如下时计算H:

H=0;
For (i=1; i<=n; i++) {
    For (j=1; j<=n; j++) {
        H = H + totient(i) * totient(j);
    }
}

totient(n)这里是n的欧拉Totient函数。完整问题可用here .

解决方案总结

问题给出的伪代码是一种计算H的朴素方法。经观察，H其实是1到n的totient函数之和，给定n，平方。我的解决方案是使用筛子生成最大 sqrt(10^4) = 10^2 的素数列表，并使用所述筛子生成数字 1 到 10^4 的欧拉 Totient 函数值以找到它主要因素和使用 Euler's product formula .然后，我只需要对上述计算值求和并平方即可得到 H。

筛和计算欧拉Totient函数值的代码可用here .我的代码已被在线评委接受(在添加了我链接的代码中未包含的求和部分和平方部分之后)。

问题

我注意到 Euler 的 Totient 函数值的总和有些奇怪:1, 2, 4, 6, 10, 12, 18, 22, 28, 32, 42, 46, 58, 64, 72，从 i = 1 到 i = 15。看起来它可能是一些自定义的数学序列，我们可以直接计算 i-th Euler's Totient 函数值，而无需使用某些数学公式对 Euler's Totient 值本身求和。所以我搜索谷歌并找到this .

我感兴趣的一个特定部分是这部分:

Sum_{k=1..n} phi(k) gives the number of distinct arithmetic progressions which contain an infinite number of primes and whose difference does not exceed n. E.g., {1k+1}, {2k+1}, {3k+1, 3k+2}, {4k+1, 4k+3}, {5k+1, ..5k+4} means 10 sequences. - Labos Elemer, May 02 2001

但是要么文本格式不正确，要么我对数学太健忘以至于无法理解它的意思。我不知道 {1k+1} 等是什么意思。然而，我的直觉告诉我它是一些序列，可以用一些数学函数来表示，或者至少可以简化，这样我就不必计算高达 N 的欧拉 Totient 值，我认为会快很多。有人可以提供更好的解决方案来计算欧拉的 Totient 函数值之和直到 N 吗？

Answer 1

如果您可以计算给定数字 n 的因式分解，那么您可以很容易地找到 Euler 的 Totient 函数的值。所以让我们假设:

n = p1^k1 * p2^k2 * ... * pn^kn

然后:

H = n * (1 - 1/p1) * (1 - 1/p2) * .... * (1 - 1/pn)

例如:

n = 24 = 2 * 2 * 2 * 3
H = 24 * (1 - 1/2) * (1 - 1/3) = 24 * 1/2 * 2/3 = 24 * 1/3 = 8

实现中可能有点棘手的是在计算中使用分数而不是小数。否则您可能不会收到整数作为最终结果。

可以找到更多信息，包括上述公式背后的推理 here .