我一直在尝试解决这个问题,但是我很难理解它:
令φ为欧拉函数,即对于自然数n,φ(n)表示满足gcd(k,n)=1的k(1 <= k <= n)的数量。
通过迭代φ,每个正整数都会生成一个以1结尾的递减序列。 例如,如果我们从5开始,将生成序列5,4,2,1。 下面是所有长度为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
只有两个这样的数列以质数开头,它们的和为12。
小于40000000的所有产生长度为25的质数之和是多少?
我的理解是φ(5)是4、2、1——即与5互质的数是4、2和1——但为什么3不在这个列表中呢?至于8,我会说4和2不与8互质...
我想我一定误解了问题...
假设问题用词不当,而φ(5)是4、3、2、1作为长度为4的链。我没有发现任何小于40m的质数生成长度为25的链——我找到了一些长度为24的链,但它们与非质数有关。