Computing Order Statistics in the Farey Sequence

Abstract

We study the problem of computing the k-th term of the Farey sequence of order n, for given n and k. Several methods for generating the entire Farey sequence are known. However, these algorithms require at least quadratic time, since the Farey sequence has Θ(n ²) elements. For the problem of finding the k-th element, we obtain an algorithm that runs in time O(n lg n) and uses space $O(\sqrt{n})$ . The same bounds hold for the problem of determining the rank in the Farey sequence of a given fraction. A more complicated solution can reduce the space to O(n ^1/3(lg lg n)^2/3) , and, for the problem of determining the rank of a fraction, reduce the time to O(n). We also argue that an algorithm with running time O(poly(lg n)) is unlikely to exist, since that would give a polynomial-time algorithm for integer factorization.