「Project Euler 441」The inverse summation of coprime couples

Posted on | Edited on | In , ,

Problem

Description

定义 R(n) 为所有满足以下条件的数对 (p, q) 的 \frac{1}{pq} 之和：

  1. 1\le p<q\le n
  2. p+q\ge n
  3. (p, q)=1

定义 S(n) ：

S(n)=\sum_{i=2}^{n}R(i)

如 S(2)=R(2)=\frac{1}{2}, S(10)\approx 6.9147, S(100)\approx 58.2962 。
求 S(10^{7}) 。

要求精确到小数点后 4 位。

Solution

Analysis

易知所求即：

\begin{aligned} &\sum_{i = 1}^{n}\sum_{p = 1}^{i}\sum_{q = p + 1}^{i}\frac{\left[p+q\ge i\right]\left[(p, q)=1\right]}{pq}\\ &= \sum_{i = 1}^{n}\sum_{p = 1}^{i}\sum_{q = p + 1}^{i}\frac{\left[p+q\ge i\right]\sum_{d |(p, q)}\mu(d)}{pq}\\ &= \sum_{i = 1}^{n}\sum_{d = 1}^{n}\mu(d)\sum_{p = 1}^{i / d}\sum_{q = p + 1}^{i / d}\frac{\left[pd+qd\ge i\right]}{pd\cdot qd}\\ &= \sum_{i = 1}^{n}\sum_{d = 1}^{n}\frac{\mu(d)}{d^{2}}\sum_{p = 1}^{i / d}\sum_{q = p + 1}^{i / d}\left(\frac{[p + q \ge i / d]}{pq}-\frac{\left[d\nmid i\right]\left[p+q=i / d\right]}{pq}\right) \end{aligned}

令：

f(n)=\sum_{p = 1}^{n}\sum_{q = p + 1}^{n}\frac{[p + q \ge n]}{pq}

g(n)=\sum_{p = 1}^{n}\sum_{q = p + 1}^{n}\frac{[p + q = n]}{pq}

令 h(n) 为调和级数 ( Harmonic Number ) ：

h(n)=\sum_{i = 1}^{n}\frac{1}{i}

考虑如何计算 f(n) 与 g(n) 。

\begin{aligned} f(n) &= \sum_{p = 1}^{n}\sum_{q = p + 1}^{n}\frac{[p + q \ge n]}{pq}\\ &= \sum_{p = 1}^{n-1}\sum_{q = p + 1}^{n-1}\left(\frac{\left[p+q\ge n-1\right]}{pq}-\frac{\left[p+q=n-1\right]}{pq}\right)+\sum_{i = 1}^{n-1}\frac{1}{i\cdot n}\\ &= f(n - 1)-g(n - 1)+\frac{h(n - 1)}{n} \end{aligned}

\begin{aligned} g(n) &= \sum_{p = 1}^{n}\sum_{q = p + 1}^{n}\frac{[p + q = n]}{pq}\\ &= \frac{1}{2}\left(\sum_{p = 1}^{n-1}\frac{1}{p\left(n-p\right)}-\frac{\left[2 | n\right]}{\left(\frac{n}{2}\right)^{2}}\right)\\ &= \frac{1}{2}\left(\sum_{p = 1}^{n-1}\frac{1}{n}\left(\frac{1}{p}+\frac{1}{n-p}\right)-\frac{4\left[2 | n\right]}{n^{2}}\right)\\ &= \frac{1}{2}\left(2\sum_{p = 1}^{n-1}\frac{1}{np}-\frac{4\left[2 | n\right]}{n^{2}}\right)\\ &= \sum_{p = 1}^{n-1}\frac{1}{np}-\frac{2\left[2 | n\right]}{n^{2}}\\ &= \frac{h(n - 1)}{n}-\frac{2\left[2 | n\right]}{n^{2}} \end{aligned}

此时有：

\begin{aligned} &\sum_{i = 1}^{n}\sum_{d = 1}^{n}\frac{\mu(d)}{d^{2}}\sum_{p = 1}^{i / d}\sum_{q = p + 1}^{i / d}\left(\frac{[p + q \ge i / d]}{pq}-\frac{\left[d\nmid i\right]\left[p+q=i / d\right]}{pq}\right)\\ =& \sum_{i = 1}^{n}\sum_{d = 1}^{n}\frac{\mu(d)}{d^{2}}\left(f\left(i / d\right)-\left[d\nmid i\right]g\left(i / d\right)\right)\\ =& \sum_{d = 1}^{n}\frac{\mu(d)}{d^{2}}\sum_{i=d}^{n}\left(f\left(i / d\right)-\left[d\nmid i\right]g\left(i / d\right)\right) \end{aligned}

按 i / d 的值分段计算即可。

关于这个题还有一个很有趣的结论（即任之洲课件中「奥妙重重的做法」），可见此处.

时间复杂度 O\left(n\ln{n}\right) 。

Code

1
巨坑待填/光速逃

References

Harmonic Number