分数序列

给定正整数$k$，按如下方式定义$a_i=x_i/y_i$：初值$a_1=1/k$，之后有 $$a_{i+1}=\frac{x_i+1}{y_i-1},$$ 并约分到最简分数，直到某个$a_k$为某个整数n时为止，并记$f(k)=n$。例如$k=20$时有 $$\frac{1}{20}\mapsto\frac{2}{19}\mapsto\frac{3}{18}=\frac{1}{6}\mapsto\frac{2}{5}\mapsto\frac{3}{4}\mapsto\frac{4}{3}\mapsto\frac{5}{2}\mapsto\frac{6}{1}=6,$$ 即$f(20)=6$。可以验证$f(1)=1,f(2)=2,f(3)=1$，以及$\sum_{k=1}^{100}f(k^3)=118937$。

求$\sum_{k=1}^{2\times 10^6}f(k^3)$。

本题难度:

解答

注意到只要不发生约分，那么分子分母之和就不变，其初值为$k+1$。

此时，分子不断增大，分母不断减小，因此第一次约分发生在分子首次达到$k+1$的最小素因子时。

重复上述过程即得$f(k)=p-1$，其中$p$是$k+1$的最大素因子。

记$p_k$为$k^3+1$最大素因子，则$f(k^3)=p_k-1$。

由$k^3+1=(k+1)(k^2-k+1)$知$p_k$或者是$k+1$的最大素因子，或者是$k^2-k+1$的最大素因子。

用筛法求出$p_k$再汇总即可，其中对$k^2-k+1$应用筛法的情形与第216题的解法类似。

最终结果是$269533451410884183$。

target=2000000
d1=[0]*(target+2)
d2=[0]*(target+2)

for i in range(2,target+2):
    if d1[i]==0:
        for j in range(i,target+2,i):
            d1[j]=i

b=[i*i-i+1 for i in range(target+1)]

for i in range(2,target+1):
    p=b[i]
    if p>1:
        for j in range(i,target+1,p):
            while b[j]%p==0:
                b[j]/=p
                d2[j]=max(d2[j],p)
        for j in range(p-i+1,target+1,p):
            while b[j]%p==0:
                b[j]/=p
                d2[j]=max(d2[j],p)

print sum(max(d1[i+1],d2[i])-1 for i in range(1,target+1))