Problem

Source: Brazilian Mathematical Olympiad 2024, Level 3, Problem 6

Tags: number theory, Farey



Let \( n > 1 \) be a positive integer. List in increasing order all the irreducible fractions in the interval \([0, 1]\) that have a positive denominator less than or equal to \( n \): \[ \frac{0}{1} = \frac{p_0}{q_0} < \frac{p_1}{q_1} < \cdots < \frac{p_M}{q_M} = \frac{1}{1}. \] Determine, in function of \( n \), the smallest possible value of \( q_{i-1} + q_i + q_{i+1} \), for \( 0 < i < M \). For example, if \( n = 4 \), the enumeration is \[ \frac{0}{1} < \frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4} < \frac{1}{1}, \]where \( p_0 = 0, p_1 = 1, p_2 = 1, p_3 = 1, p_4 = 2, p_5 = 3, p_6 = 1, q_0 = 1, q_1 = 4, q_2 = 3, q_3 = 2, q_4 = 3, q_5 = 4, q_6 = 1 \), and the minimum is \( 1 + 4 + 3 = 3 + 2 + 3 = 3 + 4 + 1 = 8 \).