Project Euler 71

题目

Ordered fractions

Consider the fraction, $\dfrac{n}{d}$, where n and d are positive integers. If $n<d$ and $\gcd(n,d)=1$, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for $d \leq 8$ in ascending order of size, we get:

$$\dfrac{1}{8},\dfrac{1}{7},\dfrac{1}{6},\dfrac{1}{5},\dfrac{1}{4},\dfrac{2}{7},\dfrac{1}{3},\dfrac{3}{8},\mathbf{\dfrac{2}{5}},\dfrac{3}{7},\dfrac{1}{2},\dfrac{4}{7},\dfrac{3}{5},\dfrac{5}{8},\dfrac{2}{3},\dfrac{5}{7},\dfrac{3}{4},\dfrac{4}{5},\dfrac{5}{6},\dfrac{6}{7},\dfrac{7}{8}$$

It can be seen that $\dfrac{2}{5}$ is the fraction immediately to the left of $\dfrac{3}{7}$.
By listing the set of reduced proper fractions for $d \leq 1,000,000$ in ascending order of size, find the numerator of the fraction immediately to the left of $\dfrac{3}{7}$.

解决方案

本题所描述的序列为Farey 序列。该序列有如下性质：

对于任意的Farey 序列$F_n$，其中任意连续的三个分数序列$\dfrac{x_1}{y_1},\dfrac{x_2}{y_2},\dfrac{x_3}{y_3}$，满足$\dfrac{x_2}{y_2}=\dfrac{x_1+x_3}{y_1+y_3}$。

本题目前比$\dfrac{3}{7}$小的最大分数为$\dfrac{2}{5}$，在中间插入一个新值$\dfrac{3+2}{7+5}=\dfrac{5}{12}$后，可以发现这个新值比$\dfrac{2}{5}$更大，但同时还是比$\dfrac{3}{7}$小。在$\dfrac{5}{12}$和$\dfrac{3}{7}$中间继续插入后，得到$\dfrac{8}{19}…$

以此类推，每插入一个新的数，分子增长$3$，分母增长了$7$，新插入值的序列可以用$\dfrac{2+3k}{5+7k}$来表示。

因此，所求分数的值满足最大的$k$使得$5+7k\leq 10^6$。

代码

N = 10 ** 6
ru, rd = 3, 7
lu, ld = 2, 5

k = (N - ld) // rd
ans = lu + ru * k
print(ans)