Data Modelling & AI Data Structure & Algorithm

Farey Sequence

23 June 2025

0

Farey sequence is a sequence which is generated for order n. The sequence has all rational numbers in range [0/0 to 1/1] sorted in increasing order such that the denominators are less than or equal to n and all numbers are in reduced forms i.e., 4/4 cannot be there as it can be reduced to 1/1.
Examples:

F1 = 0/1, 1/1
F2 = 0/1, 1/2, 1/1
F3 = 0/1, 1/3, 1/2, 2/3, 1/1
.
.
F7 = 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5,
     3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5,
     5/6, 6/7, 1/1

Farey sequence is used in rational approximations of irrational numbers, ford circles and
in Riemann hypothesis (See this for more details)
How to generate Farey Sequence of given order?
The idea is simple, we consider every possible rational number from 1/1 to n/n. And for every generated rational number, we check if it is in reduced form. If yes, then we add it to Farey Sequence. A rational number is in reduced form if GCD of numerator and denominator is 1.
Below is the implementation based on above idea.

C++

// C++ program to print Farey Sequence of given order
#include <bits/stdc++.h>
using namespace std;
 
// class for x/y (a term in farey sequence
class Term {
public:
    int x, y;
 
    // Constructor to initialize x and y in x/y
    Term(int x, int y)
        : x(x), y(y)
    {
    }
};
 
// Comparison function for sorting
bool cmp(Term a, Term b)
{
    // Comparing two ratio
    return a.x * b.y < b.x * a.y;
}
 
// GCD of a and b
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
// Function to print Farey sequence of order n
void farey(int n)
{
    // Create a vector to store terms of output
    vector<Term> v;
 
    // One by one find and store all terms except 0/1 and n/n
    // which are known
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j)
 
            // Checking whether i and j are in lowest term
            if (gcd(i, j) == 1)
                v.push_back(Term(i, j));
    }
 
    // Sorting the term of sequence
    sort(v.begin(), v.end(), cmp);
 
    // Explicitly printing first term
    cout << "0/1 ";
 
    // Printing other terms
    for (int i = 0; i < v.size(); ++i)
        cout << v[i].x << "/" << v[i].y << " ";
 
    // explicitly printing last term
    cout << "1/1";
}
 
// Driver program
int main()
{
    int n = 7;
    cout << "Farey Sequence of order " << n << " is\n";
    farey(n);
    return 0;
}

Java

// Java program to print Farey Sequence of given order
 
import java.util.*;
 
// class for x/y (a term in farey sequence
class Term {
    public int x, y;
 
    // Constructor to initialize x and y in x/y
    public Term(int x1, int y1)
    {
        this.x = x1;
        this.y = y1;
    }
};
 
public class GFG {
 
    // GCD of a and b
    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Function to print Farey sequence of order n
    static void farey(int n)
    {
        // Create a vector to store terms of output
        ArrayList<Term> v = new ArrayList<Term>();
 
        // One by one find and store all terms except 0/1
        // and n/n which are known
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j)
 
                // Checking whether i and j are in lowest
                // term
                if (gcd(i, j) == 1)
                    v.add(new Term(i, j));
        }
 
        // Sorting the term of sequence
        Collections.sort(v, new Comparator<Term>() {
            // Comparison function for sorting
            public int compare(Term a, Term b)
            {
                // Comparing two ratio
                return a.x * b.y - b.x * a.y;
            }
        });
 
        // Explicitly printing first term
        System.out.print("0/1 ");
 
        // Printing other terms
        for (int i = 0; i < v.size(); ++i)
            System.out.print(v.get(i).x + "/" + v.get(i).y
                             + " ");
 
        // explicitly printing last term
        System.out.print("1/1");
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int n = 7;
        System.out.print("Farey Sequence of order " + n
                         + " is\n");
        farey(n);
    }
}
 
// This code is contributed by phasing17

Python3

# Python3 program to print
# Farey Sequence of given order
 
# class for x/y (a term in farey sequence
class Term:
 
    # Constructor to initialize
    # x and y in x/y
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
# GCD of a and b
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
 
# Function to print 
# Farey sequence of order n
def farey(n):
 
    # Create a vector to 
    # store terms of output
    v = []
 
    # One by one find and store 
    # all terms except 0/1 and n/n
    # which are known
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
 
            # Checking whether i and j
            # are in lowest term
            if gcd(i, j) == 1:
                v.append(Term(i, j))
 
    # Sorting the term of sequence
    for i in range(len(v)):
        for j in range(i + 1, len(v)):
            if (v[i].x * v[j].y > v[j].x * v[i].y):
                v[i], v[j] = v[j], v[i]
 
    # Explicitly printing first term
    print("0/1", end = " ")
 
    # Printing other terms
    for i in range(len(v)):
        print("%d/%d" % (v[i].x, 
                        v[i].y), end = " ")
 
    # explicitly printing last term
    print("1/1")
 
# Driver Code
if __name__ == "__main__":
    n = 7
    print("Farey sequence of order %d is" % n)
    farey(n)
 
# This code is contributed by
# sanjeev2552

C#

// C# program to print Farey Sequence of given order
using System;
using System.Collections.Generic;
 
class TermComparer : Comparer<Term>
{
 
    // Comparison function for sorting
    public override int Compare(Term a, Term b)
    {
        // Comparing two ratio
        return a.x * b.y - b.x * a.y;
    }
}
 
// class for x/y (a term in farey sequence
class Term {
    public int x, y;
 
    // Constructor to initialize x and y in x/y
    public Term(int x1, int y1)
    {
        this.x = x1;
        this.y = y1;
    }
};
 
public class GFG {
 
  // GCD of a and b
  static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
 
  // Function to print Farey sequence of order n
  static void farey(int n)
  {
    // Create a vector to store terms of output
    List<Term> v = new List<Term>();
 
    // One by one find and store all terms except 0/1
    // and n/n which are known
    for (int i = 1; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j)
 
        // Checking whether i and j are in lowest
        // term
        if (gcd(i, j) == 1)
          v.Add(new Term(i, j));
    }
 
    // Sorting the term of sequence
    v.Sort(new TermComparer());
 
    // Explicitly printing first term
    Console.Write("0/1 ");
 
    // Printing other terms
    for (int i = 0; i < v.Count; ++i)
      Console.Write(v[i].x + "/" + v[i].y + " ");
 
    // explicitly printing last term
    Console.Write("1/1");
  }
 
  // Driver program
  public static void Main(string[] args)
  {
    int n = 7;
    Console.Write("Farey Sequence of order " + n
                  + " is\n");
    farey(n);
  }
}
 
// This code is contributed by phasing17

Javascript

<script>
// Javascript program to print
// Farey Sequence of given order
  
// class for x/y (a term in farey sequence
class Term
{
    // Constructor to initialize
    // x and y in x/y
    constructor(x, y)
    {
        this.x = x;
        this.y = y;
    }
}
 
 
// GCD of a and b
function gcd(a, b)
{
    if(b == 0)
        return a
    return gcd(b, a % b)    
}
 
// Function to print
// Farey sequence of order n
function farey(n)
{
    // Create a vector to
    // store terms of output
    let v = []
  
    // One by one find and store
    // all terms except 0/1 and n/n
    // which are known
    for(let i=1;i<n + 1;i++)
    {
        for(j=i+1;j<n + 1;j++)
         {
            // Checking whether i and j
            // are in lowest term
            if (gcd(i, j) == 1)
                v.push(new Term(i, j))
         }
    }
    // Sorting the term of sequence
    for(let i=0;i<(v).length;i++)
    {
        for(let j=i + 1; j<(v).length; j++)
        {
            if (v[i].x * v[j].y > v[j].x * v[i].y)
            {
                let temp = v[j];
                v[j] = v[i];
                v[i] = temp;
                 
            }
        }
     }
    // Explicitly printing first term
    document.write("0/1 ")
  
    // Printing other terms
    for(let i=0;i<(v).length;i++)
        document.write(v[i].x+"/"+v[i].y+" ")
  
    // explicitly printing last term
    document.write("1/1")
}
 
// Driver Code
let n = 7;
document.write("Farey sequence of order "+n+ " is<br>" );
farey(n)
 
// This code is contributed by patel2127
</script>

Output:

Farey Sequence of order 7 is
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 
3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1

Time complexity of above approach is O(n² Log n) where O(log n) is an upper bound on time taken by Euclid’s algorithm for GCD.
Farey Sequence has below properties [See wiki for details]
A term x/y can be recursively evaluated using previous two terms. Below is the formula to compute x_n+2/y_n+2 from x_n+1/y_n+1 and x_n/y_n.

x[n+2] = floor((y[n]+n) / y[n+1])x[n+1]– x[n]      
y[n+2] = floor((y[n]+n) / y[n+1])y[n+1]– y[n]

We can use above properties to optimize.

C++

// Efficient C++ program to print Farey Sequence of order n
#include <bits/stdc++.h>
using namespace std;
 
// Optimized function to print Farey sequence of order n
void farey(int n)
{
    // We know first two terms are 0/1 and 1/n
    double x1 = 0, y1 = 1, x2 = 1, y2 = n;
 
    printf("%.0f/%.0f %.0f/%.0f", x1, y1, x2, y2);
 
    double x, y = 0; // For next terms to be evaluated
    while (y != 1.0) {
        // Using recurrence relation to find the next term
        x = floor((y1 + n) / y2) * x2 - x1;
        y = floor((y1 + n) / y2) * y2 - y1;
 
        // Print next term
        printf(" %.0f/%.0f", x, y);
 
        // Update x1, y1, x2 and y2 for next iteration
        x1 = x2, x2 = x, y1 = y2, y2 = y;
    }
}
 
// Driver program
int main()
{
    int n = 7;
    cout << "Farey Sequence of order " << n << " is\n";
    farey(n);
    return 0;
}

Java

// Efficient Java program to print 
// Farey Sequence of order n
class GFG
{
 
// Optimized function to print 
// Farey sequence of order n
static void farey(int n)
{
    // We know first two terms are 0/1 and 1/n
    double x1 = 0, y1 = 1, x2 = 1, y2 = n;
 
    System.out.printf("%.0f/%.0f %.0f/%.0f", x1, y1, x2, y2);
 
    double x, y = 0; // For next terms to be evaluated
    while (y != 1.0) 
    {
        // Using recurrence relation to find the next term
        x = Math.floor((y1 + n) / y2) * x2 - x1;
        y = Math.floor((y1 + n) / y2) * y2 - y1;
 
        // Print next term
        System.out.printf(" %.0f/%.0f", x, y);
 
        // Update x1, y1, x2 and y2 for next iteration
        x1 = x2;
        x2 = x;
        y1 = y2;
        y2 = y;
    }
}
 
// Driver program
public static void main(String[] args)
{
    int n = 7;
    System.out.print("Farey Sequence of order " + n + " is\n");
    farey(n);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Efficient Python3 program to print
# Farey Sequence of order n
import math
 
# Optimized function to print Farey 
# sequence of order n
def farey(n):
     
    # We know first two terms are 
    # 0/1 and 1/n
    x1 = 0; 
    y1 = 1; 
    x2 = 1; 
    y2 = n;
     
    print(x1, end = "") 
    print("/", end = "")
    print(y1, x2, end = "") 
    print("/", end = "") 
    print(y2, end = " ");
 
    # For next terms to be evaluated
    x = 0;
    y = 0; 
    while (y != 1.0):
         
        # Using recurrence relation to
        # find the next term
        x = math.floor((y1 + n) / y2) * x2 - x1;
        y = math.floor((y1 + n) / y2) * y2 - y1;
 
        # Print next term
        print(x, end = "")
        print("/", end = "")
        print(y, end = " ");
 
        # Update x1, y1, x2 and y2 for 
        # next iteration
        x1 = x2; 
        x2 = x; 
        y1 = y2; 
        y2 = y;
 
# Driver Code
n = 7;
print("Farey Sequence of order", n, "is");
farey(n);
 
# This code is contributed by mits

PHP

<?php
// Efficient php program to print
// Farey Sequence of order n
 
// Optimized function to print 
// Farey sequence of order n
function farey($n)
{
     
    // We know first two 
    // terms are 0/1 and 1/n
    $x1 = 0; 
    $y1 = 1; 
    $x2 = 1; 
    $y2 = $n;
     
        echo $x1, "/", $y1, 
             " ", $x2, "/", 
             $y2, " ";
 
    // For next terms
    // to be evaluated
    $x;
    $y = 0; 
    while ($y != 1.0)
    {
         
        // Using recurrence relation to
        // find the next term
        $x = floor(($y1 + $n) / $y2) * $x2 - $x1;
        $y = floor(($y1 + $n) / $y2) * $y2 - $y1;
 
        // Print next term
        echo $x, "/", $y, " ";
 
        // Update x1, y1, x2 and
        // y2 for next iteration
        $x1 = $x2; 
        $x2 = $x; 
        $y1 = $y2; 
        $y2 = $y;
    }
}
 
    // Driver Code
    $n = 7;
    echo "Farey Sequence of order ", $n, " is\n";
    farey($n);
 
// This code is contributed by ajit
?>

C#

// Efficient C# program to print 
// Farey Sequence of order n
using System;
 
public class GFG
{
  
// Optimized function to print 
// Farey sequence of order n
static void farey(int n)
{
    // We know first two terms are 0/1 and 1/n
    double x1 = 0, y1 = 1, x2 = 1, y2 = n;
  
    Console.Write("{0:F0}/{1:F0} {2:F0}/{3:F0}", x1, y1, x2, y2);
  
    double x, y = 0; // For next terms to be evaluated
    while (y != 1.0) 
    {
        // Using recurrence relation to find the next term
        x = Math.Floor((y1 + n) / y2) * x2 - x1;
        y = Math.Floor((y1 + n) / y2) * y2 - y1;
  
        // Print next term
        Console.Write(" {0:F0}/{1:F0}", x, y);
  
        // Update x1, y1, x2 and y2 for next iteration
        x1 = x2;
        x2 = x;
        y1 = y2;
        y2 = y;
    }
}
  
// Driver program
public static void Main(String[] args)
{
    int n = 7;
    Console.Write("Farey Sequence of order " + n + " is\n");
    farey(n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Efficient javascript program to print 
// Farey Sequence of order n    
// Optimized function to print
    // Farey sequence of order n
    function farey(n) 
    {
     
        // We know first two terms are 0/1 and 1/n
        var x1 = 0, y1 = 1, x2 = 1, y2 = n;
 
        document.write(x1+"/"+y1+" "+x2+"/"+y2+" ");
 
        var x, y = 0; // For next terms to be evaluated
        while (y != 1.0)
        {
         
            // Using recurrence relation to find the next term
            x = Math.floor((y1 + n) / y2) * x2 - x1;
            y = Math.floor((y1 + n) / y2) * y2 - y1;
 
            // Print next term
            document.write(x+"/"+ y+" ");
 
            // Update x1, y1, x2 and y2 for next iteration
            x1 = x2;
            x2 = x;
            y1 = y2;
            y2 = y;
        }
    }
 
    // Driver program    
        var n = 7;
        document.write("Farey Sequence of order " + n + " is<br/>");
        farey(n);
 
// This code is contributed by gauravrajput1 
</script>

Output:

Farey Sequence of order 7 is
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 
3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1

Time Complexity of this solution is O(n)
References:
https://en.wikipedia.org/wiki/Farey_sequence
This article is contributed by Utkarsh Trivedi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

1 COMMENT

ราคา filler 25 May 2026 At 4:45 am

… [Trackback]

[…] Find More Information here to that Topic: geeksforgeeks.org/farey-sequence/ […]

Log in to leave a comment

Farey Sequence

C++

Java

Python3

C#

Javascript

C++

Java

Python3

PHP

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

EDITOR PICKS

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

POPULAR POSTS

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

POPULAR CATEGORY

ABOUT US

FOLLOW US