Project Euler 192

题目

Best Approximations

Let x be a real number.

A best approximation to \(x\) for the denominator bound \(d\) is a rational number \(\dfrac{r}{s}\) in reduced form, with \(s \le d\), such that any rational number which is closer to \(x\) than \(\dfrac{r}{s}\) has a denominator larger than \(d\):

\[\left|\dfrac{p}{q}-x\right| < \left|\dfrac{r}{s}-x\right| \Rightarrow q > d\]

For example, the best approximation to \(\sqrt{13}\) for the denominator bound \(20\) is \(\dfrac{18}{5}\) and the best approximation to \(\sqrt{13}\) for the denominator bound \(30\) is \(\dfrac{101}{28}\).

Find the sum of all denominators of the best approximations to \(\sqrt{n}\) for the denominator bound \(10^{12}\), where \(n\) is not a perfect square and \(1 < n \le 100000\).

解决方案

令\(M=10^{12}\)。如果需要求无理数\(\sqrt{n}\)的有理近似，那么我们将在Stern-Brocot Tree上“尝试”查找这个数。（这里使用的Stern-Brocot Tree是全体最简分数，因此最小值为\(0\)，最大值则推广到无穷。）

最终，寻找到两个候选答案\(\dfrac{a}{c},\dfrac{b}{d}\)，满足\(\dfrac{a}{c}<\sqrt{n}<\dfrac{b}{d},c,d \le M\)。判断这两个分数谁比较接近即可。

为了避免浮点数产生的误差，进行浮点数比较时会转成整数之间的比较：

1. 比较分数\(\dfrac{p}{q}\)和\(\sqrt{n}\)，相当于比较\(p^2\)和\(nq^2\)的大小。
2. 比较\(\sqrt{n}-\dfrac{a}{c}\)和\(\dfrac{b}{d}-\sqrt{n}\)，经转化后，相当于比较\(4nc^2d^2\)和\((bc+ad)^2\)的大小。

另一个用有理数近似无理数的相关的方法是基于连分数的，在该页面中有介绍。

代码

N = 10 ** 5
M = 10 ** 12


def cal(n):
    a, c = 0, 1
    b, d = 1, 0
    while True:
        p = a + b
        q = c + d

        if q > M:
            if 4 * n * c ** 2 * d ** 2 < (a * d + b * c) ** 2:
                return c
            else:
                return d
        else:
            t = p * p - q * q * n
            if t == 0:
                # 找到了一个有理数p/q，其值为sqrt(n)，这说明n是个平方数，不是我们需要求的。
                break
            if t > 0:
                b, d = p, q
            else:
                a, c = p, q
    return 0


ans = sum(cal(x) for x in range(2, N + 1))
print(ans)