13.分数有范围计数

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

将所有 $d \leq 8$ 的最简真分数构成的集合按大小升序排列: \(\begin{gathered} 1 / 8,1 / 7,1 / 6,1 / 5,1 / 4,2 / 7,1 / 3, \mathbf{3} / 8, \mathbf{2} / \mathbf{5}, \mathbf{3} / 7,1 / 2 \\ 4 / 7,3 / 5,5 / 8,2 / 3,5 / 7,3 / 4,4 / 5,5 / 6,6 / 7,7 / 8 \end{gathered}\)

可以看出在 $1 / 3$ 和 $1 / 2$ 之间有 3 个分数。 将 $d \leq 12,000$ 的最简真分数构成的集合排序后，在 $1 / 3$ 和 $1 / 2$ 之间有多少个分数?

Answer: 7295372