MathDB

For each positive integer

n

, list in increasing order all irreducible fractions in the interval

[0, 1]

that have a positive denominator less than or equal to

n

0 = \frac{p_0}{q_0} < \frac{1}{n} = \frac{p_1}{q_1} < \cdots < \frac{1}{1} = \frac{p_{M(n)}}{q_{M(n)}}.

Let

k

be a positive integer. We define, for each

n

such that

M(n) \geq k - 1

f_k(n) = \min \left\{ \sum_{s=0}^{k-1} q_{j+s} : 0 \leq j \leq M(n) - k + 1 \right\}.

Determine, in function of

k

\lim_{n \to \infty} \frac{f_k(n)}{n}.

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

and

q_0 = 1, q_1 = 4, q_2 = 3, q_3 = 2, q_4 = 3, q_5 = 4, q_6 = 1

. In this case, we have

f_1(4) = 1, f_2(4) = 5, f_3(4) = 8, f_4(4) = 10, f_5(4) = 13, f_6(4) = 17

, and

f_7(4) = 18

Problem Statement