Problem 72

Counting 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 there are $21$ elements in this set.

How many elements would be contained in the set of reduced proper fractions for $d \leq 1, 000, 000$ ?

考虑形如 $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$

可以看出该集合中共有 $21$ 个元素。

所有 $d \leq 1, 000, 000$ 的最简真分数构成的集合中共有多少个元素？