分母が $n$ 以下かつ $0$ 以上 $1$ 以下であるような既約分数を小さい順に並べてできる数列 $F_n$ をファレイ数列 (Farey sequence) といいます。この問題は $F_n$ の $x$ 項目を求める問題に帰着されます。
ここで、ファレイ数列の性質として、以下があります。

これを利用し、再帰関数を用いて \(F_M\) を前から順に構築していくことでこの問題を解くことができます。