Farey Sequence In C++

In this post, we will explore the Farey series, its mathematical characteristics, and the optimal method to produce it using C++.

Overview:

One significant mathematical concept that is relevant in the realms of fractions and number theory is the Farey sequence. The Farey sequence represents a series of reduced fractions in ascending order from 0 to 1, wherein the denominator of each fraction may be equal to or less than a specified value, denoted as 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++:

To efficiently generate the Farey sequence, we utilize the mediant property, which ensures that given any two fractions a/b and c/d, their mediant (a + c) / (b + d) is positioned between them within the sequence.

Method 1: Brute Force

One straightforward method involves generating all potential fractions, simplifying them, and then organizing them in order. Nonetheless, this technique proves to be ineffective when dealing with significant values of 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 effective method for computing F(n) involves leveraging the Farey neighbors property, which helps eliminate unnecessary computations.

#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 summary, the Farey sequence represents a captivating mathematical concept with significant characteristics and practical uses. While the brute-force method is logical, leveraging Farey's property simplifies the sequence generation to O(n), ensuring efficiency even with large n values.