从1到N的欧拉函数的有效和

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的欧拉函数。完整的问题是可用的这里。

解决方案摘要

这个问题给出的伪码是计算H的一种天真的方法。经过观察，H实际上是从1到n的函数之和，给定n，平方。我的解决方案是使用筛子生成到sqrt(10^4) = 10^2的素数列表，并使用所述筛子生成1到10^4的欧拉函数值，以求其素数因子，并使用欧拉积公式。然后，我只需要对所述的计算值进行求和，并将其平方以得到H。

筛选和计算欧拉函数值的代码是可用的这里。我的代码已经被在线评审所接受(在添加了不包括在我链接的代码中的求和部分和平方部分之后)。

问题

我注意到欧拉函数值之和中的一些奇怪之处：1, 2, 4, 6, 10, 12, 18, 22, 28, 32, 42, 46, 58, 64, 72，从i = 1到i = 15。它似乎是一些自定义的数学序列，我们可以直接计算i-th欧拉函数的值，而不需要用一些数学公式来求和欧拉的整体值。于是我搜索了谷歌并找到了这。

我感兴趣的一个部分是：

Sum_{k=1..n} phi(k)给出了包含无限个素数且其差值不超过n的不同算术进展数，例如，{1k+1}、{2k+1}、{3k+1、3k+2}、{4k+1、4k+3}、{5k+1、..5k+4}表示10个序列。- Labos Elemer，2001年5月2日

但是，要么这篇文章的格式很糟糕，要么我在数学上太忘却了，以至于我无法理解它的含义。我不知道{1k+1}等是什么意思。然而，我的直觉告诉我，它是一个序列，可以用一些数学函数来表示，或者至少简化，这样我就不必计算欧拉的整体值，直到N，我认为它会快得多。有人能给出一个更好的解决方案来计算欧拉函数值到N的和

Answer 1

如果你能计算给定数n的因式分解，那么你就可以很容易地找到欧拉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

在实现中可能有点棘手的是在计算中使用分数而不是十进制数。否则，您可能不会接收一个整数作为最终结果。

更多的信息，包括上面公式背后的推理，可以找到这里。

Answer 2

在OEIS中，A002088被称为A005728负1 ("Wolfdieter，2016年11月22日“)。对于A005728，有一些公式(“DavidW.Wilson，2002年5月25日”)：a(n) = n(n+3)/2 - Sum(k = 2 to n, a([n/k]))。

这个公式似乎相当快。一个未优化的Python程序在大约10秒钟内计算出头10000个数字。

num = 10000
a = [1] + [0] * num
for n in range(1, num+1):
    a[n] = n * (n+3) // 2
    for k in range(2, n+1):
        a[n] -= a[n // k]
print(a)

顺便说一句，要计算totient函数，不需要任何分数，一切都可以用整数算法来完成：

def phi(n):
    prod = n
    for i in set(prime_factors(n)):
        # prod = prod * (1 - 1 / i)
        prod = prod * (i - 1) // i  # rewrite the formula to only work with integers
    return int(prod)

PS:我也不明白Labos Elemer的话。这让我想到了孪生素猜想，这个猜想还没有得到证实。无论如何，它并没有给人一个快速公式的印象。