给定整数M，令$R(M)$为所有$1/(pq)$之和，其中p,q取遍满足$1\le p < q\le M, p+q\ge M, \gcd(p,q)=1$的数对。

再令$S(N)=\sum_{i=2}^NR(i)$，可以验证$S(2)=R(2)=1/2$，$S(10)\approx6.9147$以及$S(100)\approx58.2962$。

求$S(10^7)$，结果保留4位小数。

本题难度:

解答

首先可以归纳验证这样如下并不显然的等式： $$\sum_{\substack{1\le p,q\le m-1 \\ \gcd(p,q)=1 \\ p+q\ge m}}=1.$$ 与$R(m)$的定义比较可得 $$R(m)=\frac{1}{2} +\frac{1}{m}\sum_{\substack{1\le p < m\\ \gcd(p,m)=1}}\frac{1}{p}.$$ 再汇总即得结果$5000088.8395$。

注：因求和中用到莫比乌斯反演并使用sympy计算莫比乌斯函数，以下代码为Python 3。

from sympy import sieve 

N=10000000

s1=s2=0
g=[0]

for k in range(1,N+1):
    g.append(g[-1]+s1/k)
    s1+=1/k
    s2+=1/(k*k)
    
mu=list(sieve.mobiusrange(1,N+1))

print("{0:.4f}".format(0.5*(N-2+s1*s1-s2)+sum(mu[r-1]*g[N//r]/(r*r) for r in range(2,N+1))))