Project Euler 72

题目

Counting fractions

Consider the fraction, ${\displaystyle \frac{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\le 8$ in ascending order of size, we get:

$${\displaystyle \frac{1}{8}},{\displaystyle \frac{1}{7}},{\displaystyle \frac{1}{6}},{\displaystyle \frac{1}{5}},{\displaystyle \frac{1}{4}},{\displaystyle \frac{2}{7}},{\displaystyle \frac{1}{3}},{\displaystyle \frac{3}{8}},{\displaystyle \frac{2}{5}},{\displaystyle \frac{3}{7}},{\displaystyle \frac{1}{2}},{\displaystyle \frac{4}{7}},{\displaystyle \frac{3}{5}},{\displaystyle \frac{5}{8}},{\displaystyle \frac{2}{3}},{\displaystyle \frac{5}{7}},{\displaystyle \frac{3}{4}},{\displaystyle \frac{4}{5}},{\displaystyle \frac{5}{6}},{\displaystyle \frac{6}{7}},{\displaystyle \frac{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\le 1,000,000$?

解决方案

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

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

$$\sum _{i=1}^m\phi (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)