Project Euler 72

题目

Counting 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},\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 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$?

解决方案

根据题意，第$m$个Farey 序列$F_m$的所有元素可以由该集合定义：$\left{\dfrac{n}{d} | \gcd(n,d)=1,1\le n<d \le m\right}$.

通过分子分母互质的性质，联系到欧拉函数$\varphi$的定义，可以得出本题答案：

$$\sum_{i=1}^m \varphi(i)-1$$

代码

N = 1000000
phi = [i for i in range(N + 1)]
for i in range(2, N + 1):
    if i == phi[i]:
        for j in range(i, N + 1, i):
            phi[j] //= i
            phi[j] *= i - 1
ans = sum(phi) - 1
print(ans)