Farey Sequence In C++

In this article, we will discuss the Farey sequence, its mathematical properties, and how to efficiently generate it using C++.

Overview:

One important mathematical idea that has applications in fractions and number theory is the Farey sequence. The Farey sequence is an order of fully minimized fractions with rising values from 0 to 1, where each fraction’s denominator is possibly equivalent to or less than a certain number, n.

Understanding the sequence:

For any given positive integer n, the Farey sequence of order n, abbreviated as F(n), is all fractions a/b such that:

• ✅ 0 ≤ a ≤ b ≤ n
• ✅ gcd(a, b) = 1 (i.e., the fraction is in simplest form)
• ✅ The fractions are listed in ascending order.

Example: Farey for n = 4

F(4) = { 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1 }

Explanation:

• ✅ The denominators are between 1 and 4.
• ✅ Only fractions in the simplest form are included.
• ✅ The fractions are arranged in ascending order.

Properties:

• ✅ Symmetry: All Farey sequences F(n) are symmetric about 1/2.
• ✅ Number of Terms: The total number of fractions in F(n) is: |F(n)| = 1 + Σ φ(k) (for k = 1 to n) where φ(k) is Euler's totient function, i.e., counts numbers less than k and coprime to k.
• ✅ Farey Neighbors: If a/b and c/d are consecutive terms in F(n), bc - ad = 1. This property efficiently generates the sequence.

Implementing in C++:

In order to compute the Farey sequence effectively, we employ the mediant property, which guarantees that for any two fractions a/b and c/d. Their mediant (a + c) / (b + d) lies between them in the sequence.

Method 1: Brute Force

A simple approach is to generate all possible fractions, simplify them, and sort them. However, this method is inefficient for large n.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>  
using namespace std;
struct Fraction {
    int num, den;
    bool operator<(const Fraction& other) const {
        return num * other.den < den * other.num;
    }
};
vector<Fraction> fareySequence(int n) {
    vector<Fraction> fractions;
fractions.push_back({0, 1});
    for (int d = 1; d <= n; d++) {
        for (int num = 1; num <= d; num++) {
            if (gcd(num, d) == 1) {
                fractions.push_back({num, d});
            }
        }
    }
fractions.push_back({1, 1});
    sort(fractions.begin(), fractions.end());
    return fractions;
}
int main() {
    int n = 4;
    vector<Fraction> result = fareySequence(n);
    for (const auto& frac : result) {
        cout << frac.num << "/" << frac.den << " ";
    }
    return 0;
}

Output:

0/1 1/4 1/3 1/2 2/3 3/4 1/1 1/1

Complexity Analysis:

• ✅ Generating Fractions: O(n^2)
• ✅ Sorting: O(n log n)
• ✅ Total Complexity: O(n^2 log n) (not optimal for large n)

Method 2: Farey Sequence Property

A more efficient way to generate F(n) is using the Farey neighbors property, which avoids redundant calculations.

#include <iostream>
using namespace std;
void fareySequence(int n) 
{
    int a = 0, b = 1, c = 1, d = n;
    cout << a << "/" << b << " "; 
    while (c <= n) 
{
        int k = (n + b) / d;
        int temp_a = c, temp_b = d;
        c = k * c - a;
        d = k * d - b;
        a = temp_a;
        b = temp_b;
        cout << a << "/" << b << " ";
    }
}
int main() 
{
    int n = 4;
    fareySequence(n);
    return 0;
}

Output:

0/1 1/4 1/3 1/2 2/3 3/4 1/1

Explanation:

• ✅ Start with 0/1 and 1/n.
• ✅ Use mediant property: Generate the next term using k = (n + b) / d.
• ✅ No sorting is needed because fractions are generated in order.
• ✅ Time Complexity: O(n) (much better than brute-force O(n^2 log n)).

Applications of Farey Sequence:

Several applications of the Farey Sequence in C++ are as follows:

• ✅ Music Theory: Farey sequences help approximate musical scales.
• ✅ Computer Graphics : It is used for anti-aliasing and rendering.
• ✅ Cryptography : Euler’s totient function plays a key role in RSA encryption.
• ✅ Number Theory: It helps in rational approximations and continued fractions.

Conclusion:

In conclusion, the Farey sequence is a beautiful mathematical idea with profound properties and real-world applications. Although the brute-force approach makes sense, employing Farey’s property streamlines generating the sequence to O(n), which is efficient even for huge values of n.