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


EnableExplicit
 
Structure farey_struc
  complex.POINT
  quotient.d
EndStructure
 
#MAXORDER=1000
Global NewList fareylist.farey_struc()
 
Define v_start.i,
       v_end.i,
       v_step.i,
       order.i,
       fractions.i,
       check.b,
       t$
 
Procedure farey(order)
  NewList sequence.farey_struc()
  Define quotient.d,
         divisor.i,
         dividend.i
 
  For divisor=1 To order
    For dividend=0 To divisor
      quotient.d=dividend/divisor
      AddElement(sequence())
      sequence()\complex\x=dividend
      sequence()\complex\y=divisor
      sequence()\quotient=quotient      
    Next
  Next
 
  SortStructuredList(sequence(),#PB_Sort_Ascending,
                     OffsetOf(farey_struc\quotient),
                     TypeOf(farey_struc\quotient))
 
  FirstElement(sequence())
  quotient=sequence()\quotient  
  AddElement(fareylist())
  fareylist()\complex\x=sequence()\complex\x
  fareylist()\complex\y=sequence()\complex\y
  fareylist()\quotient=sequence()\quotient
 
  ForEach sequence()
    If quotient=sequence()\quotient : Continue : EndIf
    quotient=sequence()\quotient  
    AddElement(fareylist())
    fareylist()\complex\x=sequence()\complex\x
    fareylist()\complex\y=sequence()\complex\y
    fareylist()\quotient=sequence()\quotient    
  Next
  FreeList(sequence())
EndProcedure
 
OpenConsole("Farey sequence [Input exit = program end]")
Repeat
  Print("Input-> start end step [start>=1; end<=1000; step>=1; (start<end)] : ")
  t$=Input() : If Trim(LCase(t$))="exit" : End : EndIf
  v_start=Val(StringField(t$,1," "))
  v_end=Val(StringField(t$,2," "))
  v_step=Val(StringField(t$,3," "))
  check=Bool(v_start>=1 And v_end<=#MAXORDER And v_step>=1 And v_start<v_end)
Until check=#True
PrintN(~"\n"+LSet("-",80,"-"))
 
order=v_start
While order<=v_end
  FreeList(fareylist()) : NewList fareylist()
  farey(order)
  fractions=ListSize(fareylist())
  PrintN("Farey sequence for order "+Str(order)+" has "+Str(fractions)+" fractions.")
  If fractions<100
    ForEach fareylist()
      If ListIndex(fareylist()) % 7 = 0 : PrintN("") : EndIf
      Print(~"\t"+
             RSet(Str(fareylist()\complex\x),2," ")+"/"+
             RSet(Str(fareylist()\complex\y),2," "))
    Next
  EndIf
  PrintN(~"\n"+LSet("=",80,"="))
  order+v_step
Wend
Input()