Finding kth element in the nth order of Farey Sequence

Farey sequence of order n is the sequence of completely reduced fractions, between 0 and 1 which when in lowest terms have denominators less than or equal to n, arranged in order of increasing size. Detailed explanation here.

Problem

The problem is, given n and k, where n = order of seq and k = element index, can we find the particular element from the sequence. For examples answer for (n=5, k =6) is 1/2.

Lead

There are many less than optimal solution available, but am looking for a near-optimal one. One such algorithm is discussed here, for which I am unable to understand the logic hence unable to apply the examples.

Question

Can some please explain the solution with more detail, preferably with an example.

Thank you.

Solution

I've read the method provided in your link, and the accepted C++ solution to it. Let me post them, for reference:

Editorial Explanation

Several less-than-optimal solutions exist. Using a priority queue, one can iterate through the fractions (generating them one by one) in O(K log N) time. Using a fancier math relation, this can be reduced to O(K). However, neither of these solution obtains many points, because the number of fractions (and thus K) is quadratic in N.

The “good” solution is based on meta-binary search. To construct this solution, we need the following subroutine: given a fraction A/B (which is not necessarily irreducible), find how many fractions from the Farey sequence are less than this fraction. Suppose we had this subroutine; then the algorithm works as follows:

Determine a number X such that the answer is between X/N and (X+1)/N; such a number can be determined by binary searching the range 1...N, thus calling the subroutine O(log N) times.

Make a list of all fractions A/B in the range X/N...(X+1)/N. For any given B, there is at most one A in this range, and it can be determined trivially in O(1).

Determine the appropriate order statistic in this list (doing this in O(N log N) by sorting is good enough).

It remains to show how we can construct the desired subroutine. We will show how it can be implemented in O(N log N), thus giving a O(N log^2 N) algorithm overall. Let us denote by C[j] the number of irreducible fractions i/j which are less than X/N. The algorithm is based on the following observation: C[j] = floor(X*B/N) – Sum(C[D], where D divides j). A direct implementation, which tests whether any D is a divisor, yields a quadratic algorithm. A better approach, inspired by Eratosthene’s sieve, is the following: at step j, we know C[j], and we subtract it from all multiples of j. The running time of the subroutine becomes O(N log N).

Relevant Code

#include <cassert>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const int kMaxN = 2e5;
typedef int int32;
typedef long long int64_x;
// #define int __int128_t
// #define int64 __int128_t

typedef long long int64;


int64 count_less(int a, int n) {
    vector<int> counter(n + 1, 0);
    for (int i = 2; i <= n; i += 1) {
        counter[i] = min(1LL * (i - 1), 1LL * i * a / n);
    }

    int64 result = 0;
    for (int i = 2; i <= n; i += 1) {
        for (int j = 2 * i; j <= n; j += i) {
            counter[j] -= counter[i];
        }
        result += counter[i];
    }

    return result;
}

int32 main() {
//    ifstream cin("farey.in");
//    ofstream cout("farey.out");
    int64_x n, k; cin >> n >> k;
    assert(1 <= n);
    assert(n <= kMaxN);
    assert(1 <= k);
    assert(k <= count_less(n, n));

    int up = 0;
    for (int p = 29; p >= 0; p -= 1) {
        if ((1 << p) + up > n) 
            continue;

        if (count_less((1 << p) + up, n) < k) {
            up += (1 << p);
        }
    }

    k -= count_less(up, n);

    vector<pair<int, int>> elements;
    for (int i = 1; i <= n; i += 1) {
        int b = i;
        // find a such that up/n < a / b and a / b <= (up+1) / n
        int a = 1LL * (up + 1) * b / n;
        if (1LL * up * b < 1LL * a * n) {
        } else {
            continue;
        }

        if (1LL * a * n <= 1LL * (up + 1) * b) {
        } else {
            continue;
        }

        if (__gcd(a, b) != 1) {
            continue;
        }

        elements.push_back({a, b});
    }

    sort(elements.begin(), elements.end(), 
            [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool {
                return 1LL * lhs.first * rhs.second < 1LL * rhs.first * lhs.second; 
            });

    cout << (int64_x)elements[k - 1].first << ' ' << (int64_x)elements[k - 1].second << '\n';
    return 0;
}

Basic Methodology

The above editorial explanation results in the following simplified version. Let me start with an example.

Let's say, we want to find 7th element of Farey Sequence with N = 5.

We start with writing a subroutine, as said in the explanation, that gives us the "k" value (how many Farey Sequence reduced fractions there exist before a given fraction - the given number may or may not be reduced)

So, take your F5 sequence:

k = 0,  0/1
k = 1,  1/5
k = 2,  1/4
k = 3,  1/3
k = 4,  2/5
k = 5,  1/2
k = 6,  3/5
k = 7,  2/3
k = 8,  3/4
k = 9,  4/5
k = 10, 1/1

If we can find a function that finds the count of the previous reduced fractions in Farey Sequence, we can do the following:

int64 k_count_2 = count_less(2, 5); // result = 4
int64 k_count_3 = count_less(3, 5); // result = 6
int64 k_count_4 = count_less(4, 5); // result = 9

This function is written in the accepted solution. It uses the exact methodology explained in the last paragraph of the editorial.

As you can see, the count_less() function generates the same k values as in our hand written list.

We know the values of the reduced fractions for k = 4, 6, 9 using that function. What about k = 7? As explained in the editorial, we will list all the reduced fractions in range X/N and (X+1)/N, here X = 3 and N = 5.

Using the function in the accepted solution (its near bottom), we list and sort the reduced fractions.

After that we will rearrange our k values, as in to fit in our new array as such:

k = -,  0/1
k = -,  1/5
k = -,  1/4
k = -,  1/3
k = -,  2/5
k = -,  1/2
k = -,  3/5 <-|
k = 0,  2/3   | We list and sort the possible reduced fractions 
k = 1,  3/4   | in between these numbers
k = -,  4/5 <-|
k = -, 1/1

(That's why there is this piece of code: k -= count_less(up, n);, it basically remaps the k values)

(And we also subtract one more during indexing, i.e.: cout << (int64_x)elements[k - 1].first << ' ' << (int64_x)elements[k - 1].second << '\n';. This is just to basically call the right position in the generated array.)

So, for our new re-mapped k values, for N = 5 and k = 7 (original k), our result is 2/3.

(We select the value k = 0, in our new map)

If you compile and run the accepted solution, it will give you this:

Input:  5 7 (Enter)
Output: 2 3

I believe this is the basic point of the editorial and accepted solution.