Problem 71

Ordered Fractions

Consider the fraction, $n / d$ , where $n$ and $d$ are positive integers. If $n < d$ and $H C F (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:

$1 / 8, 1 / 7, 1 / 6, 1 / 5, 1 / 4, 2 / 7, 1 / 3, 3 / 8, 2/5, 3 / 7, 1 / 2,$
$4 / 7, 3 / 5, 5 / 8, 2 / 3, 5 / 7, 3 / 4, 4 / 5, 5 / 6, 6 / 7, 7 / 8$

It can be seen that $2 / 5$ is the fraction immediately to the left of $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 $3 / 7$ .

有序分数

考虑形如 $n / d$ 的分数，其中 $n$ 和 $d$ 均为正整数。如果 $n < d$ 且其最大公约数为 $1$ ，则称该分数为最简真分数。

将所有 $d \leq 8$ 的最简真分数构成的集合按大小升序排列：

$1 / 8, 1 / 7, 1 / 6, 1 / 5, 1 / 4, 2 / 7, 1 / 3, 3 / 8, 2/5, 3 / 7, 1 / 2,$
$4 / 7, 3 / 5, 5 / 8, 2 / 3, 5 / 7, 3 / 4, 4 / 5, 5 / 6, 6 / 7, 7 / 8$

可以看出 $2 / 5$ 是 $3 / 7$ 直接左邻的分数。

将所有 $d \leq 1, 000, 000$ 的最简真分数按大小升序排列，求此时 $3 / 7$ 直接左邻的分数的分子。