【Project Euler】Problem 71: 分数の順序

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 71. 分数の順序

原文 Problem 71: Ordered fractions

問題の要約：分母$d \le 10^6$のすべての既約真分数を値の順に並べたとき$3/7$の直前の分数の分子を求めよ

例として$d=8$の場合は$2/5$が答えとなります。

考え方としては$3/7$との差分が最小になる分数$n/d$を探せばよいので。

\frac{3}{7}-\frac{n}{d}=\frac{3d-7n}{7d}  \\
で分子3d-7n=1となる最大のdが答え \\
n=\frac{3d-1}{7}が整数

プロクラムにすると以下のようになりますが。電卓でも求まりそうです。

for d in range(10**6, 0, -1):
  if (3*d-1)%7 == 0:
    break
print(f"Answer: {(3*d-1)//7}")

（開発環境：Google Colab）