algorithm - 欧拉计划问题 214-totients，有意义吗？

Question

我一直在努力tackle this problem ，但我很难理解它:

Let φ be Euler's totient function, i.e. for a natural number n, φ(n) is the number of k, 1 <= k <= n, for which gcd(k,n) = 1.

By iterating φ, each positive integer generates a decreasing chain of numbers ending in 1.E.g. if we start with 5 the sequence 5,4,2,1 is generated.Here is a listing of all chains with length 4:

5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1

Only two of these chains start with aprime, their sum is 12.

What is the sum of all primes lessthan 40000000 which generate a chainof length 25?

我对此的理解是 φ(5) 是 4、2、1 - 即 5 的互质数是 4、2 和 1 - 但为什么 3 也不在该列表中？至于 8，我会说 4 和 2 不是 8 的互质...

我想我一定是误解了这个问题......

假设问题措辞不当，并且 φ(5) 是 4、3、2、1 作为 4 链。我没有找到任何小于 40m 的素数生成 25 链 - 我找到一些 24 的链，但它们与非质数有关。

Answer 1

“迭代函数”意味着根据自己的结果运行函数。喜欢:φ(5) = 4; φ(4) = 2; φ(2) = 1;因此，我们得到你的 5-4-2-1 链。与所有其他链式店相同。