The   Farey sequence    Fn   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.

The   Farey sequence   is sometimes incorrectly called a   Farey series.



Each Farey sequence:

   starts with the value   0   (zero),   denoted by the fraction     





0
1




{\displaystyle {\frac {0}{1}}}


   ends with the value   1   (unity),   denoted by the fraction   





1
1




{\displaystyle {\frac {1}{1}}}

.


The Farey sequences of orders   1   to   5   are:

 







F




1


=


0
1


,


1
1




{\displaystyle {\bf {\it {F}}}_{1}={\frac {0}{1}},{\frac {1}{1}}}



 







F




2


=


0
1


,


1
2


,


1
1




{\displaystyle {\bf {\it {F}}}_{2}={\frac {0}{1}},{\frac {1}{2}},{\frac {1}{1}}}



 







F




3


=


0
1


,


1
3


,


1
2


,


2
3


,


1
1




{\displaystyle {\bf {\it {F}}}_{3}={\frac {0}{1}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {1}{1}}}



 







F




4


=


0
1


,


1
4


,


1
3


,


1
2


,


2
3


,


3
4


,


1
1




{\displaystyle {\bf {\it {F}}}_{4}={\frac {0}{1}},{\frac {1}{4}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {3}{4}},{\frac {1}{1}}}



 







F




5


=


0
1


,


1
5


,


1
4


,


1
3


,


2
5


,


1
2


,


3
5


,


2
3


,


3
4


,


4
5


,


1
1




{\displaystyle {\bf {\it {F}}}_{5}={\frac {0}{1}},{\frac {1}{5}},{\frac {1}{4}},{\frac {1}{3}},{\frac {2}{5}},{\frac {1}{2}},{\frac {3}{5}},{\frac {2}{3}},{\frac {3}{4}},{\frac {4}{5}},{\frac {1}{1}}}


Task
   Compute and show the Farey sequence for orders   1   through   11   (inclusive).
   Compute and display the   number   of fractions in the Farey sequence for order   100   through   1,000   (inclusive)   by hundreds.
   Show the fractions as    n/d    (using the solidus [or slash] to separate the numerator from the denominator). 


The length   (the number of fractions)   of a Farey sequence asymptotically approaches:

  3 × n2   ÷   



π


{\displaystyle \pi }

2 
See also

   OEIS sequence   A006842 numerators of Farey series of order 1, 2, ··· 
   OEIS sequence   A006843 denominators of Farey series of order 1, 2, ··· 
   OEIS sequence   A005728 number of fractions in Farey series of order n 
   MathWorld entry   Farey sequence
   Wikipedia   entry   Farey sequence


fcn farey(n){
   f1,f2:=T(0,1),T(1,n);  // fraction is (num,dnom)
   print("%d/%d %d/%d".fmt(0,1,1,n));
   while(f2[1]>1){
      k,t  :=(n + f1[1])/f2[1], f1;
      f1,f2 = f2,T(f2[0]*k - t[0], f2[1]*k - t[1]);
      print(" %d/%d".fmt(f2.xplode()));
   }
   println();
}