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


 
 [Farey sequence for Rosetta Code website.
  EDSAC program, Initial Orders 2.
  Prints Farey sequences up to order 11
  (or other limit determined by a simple edit).]
 
 [Modification of library subroutine P6.
  Prints number (absolute value <= 65535)
  passed in 0F, without leading spaces.
  41 locations.]
          T 56 K
  GKA3FT35@SFG11@UFS40@E10@O40@T4FE35@O@T4F
  H38@VFT4DA13@TFH39@S16@T1FV4DU4DAFG36@TFTF
  O5FA4DF4FS4FL4FT4DA1FS13@G19@EFSFE30@J995FJFPD
 
          T 100 K
          G     K
  [Maximum order to be printed. For convenience, entered as
  an address, not an integer, e.g. 'P 11 F' not 'P 5 D'.]
    [0]   P  11 F [<--- edit here]
  [Other constants]
    [1]   P     D [1]
    [2]   #     F [figure shift]
    [3]   X     F [slash]
    [4]   !     F [space]
    [5]   @     F [carriage return]
    [6]   &     F [line feed]
    [7]   K4096 F [teleprinter null]
  [Variables]
    [8]   P     F [n, order of current Farey sequence]
    [9]   P     F [maximum n + 1, as integer]
          [a/b and c/d are consecutive terms of the Farey sequence]
   [10]   P     F [a]
   [11]   P     F [b]
   [12]   P     F [c]
   [13]   P     F [d]
   [14]   P     F [t, temporary store]
 
          [Subroutine to print c/d]
   [15]   A   3 F [plant link for return]
          T  26 @
          A  12 @ [load c]
          T     F [to 0F for printing]
   [19]   A  19 @ [for subroutine return]
          G  56 F [print c]
          O   3 @ [print '/']
          A  13 @ [load d]
          T     F [to 0F for printing]
   [24]   A  24 @ [for subroutine return]
          G  56 F [print d]
   [26]   E     F [return]
 
           [Main routine.
           Enter with accumulator = 0.]
   [27]   O   2 @ [set teleprinter to figures]
          A     @ [max order as address]
          R     D [shift 1 right to make integer]
          A   1 @ [add 1]
          T   9 @ [save for comparison]
          A   1 @ [start with order 1]
          [Here with next order (n) in the accumulator]
   [33]   S   9 @ [subtract (max order) + 1]
          E  84 @ [exit if over maximum]
          A   9 @ [restore after test]
          T   8 @ [store]
          [Prefix the Farey sequence with a formal term -1/0.
           The second term is calculated from this and the first term.]
          S   1 @ [acc := -1]
          T  10 @ [a := -1]
          T  11 @ [b := 0]
          T  12 @ [c := 0]
          A   1 @ [d := 1]
          T  13 @
          A  43 @ [for subroutine return]
          G  15 @ [call subroutine to print c/d]
 
          [Calculate next term; basically same as Wikipedia method]
   [45]   T     F [clear acc]
          A  10 @ [t := a]
          T  14 @
          A  12 @ [a := c;]
          T  10 @
          S  14 @ [c := -t]
          T  12 @
          A  11 @ [t := b]
          T  14 @
          A  13 @ [b := d]
          T  11 @
          S  14 @ [d := -t]
          T  13 @
          A   8 @ [t := n + t]
          A  14 @ 
          T  14 @
          [Inner loop, get t div b by repeated subtraction]
   [61]   A  14 @ [t := t - b]
          S  11 @
          G  72 @ [jump out when t < 0]
          T  14 @
          A  12 @ [c := c + a]
          A  10 @
          T  12 @
          A  13 @ [d := d + b]
          A  11 @ 
          T  13 @
          E  61 @ [loop back (always, since acc = 0)]
          [End of inner loop, print c/d preceded by space]
   [72]   O   4 @ 
          T     F
   [74]   A  74 @ [for subroutine return]
          G  15 @ [call subroutine to print c/d]
          A   1 @ [form 1 - d, to test for d = 1]
          S  13 @
          G  45 @ [if d > 1, loop for next term]
          O   5 @ [else print end of line (CR LF)]
          O   6 @
 
          [Next Farey series.]
          A   8 @ [load order]
          A   1 @ [add 1]
          E  33 @ [loop back]
 
          [Here when finished]
   [84]   O   7 @ [output null to flush teleprinter buffer]
          Z     F [stop]
          E  27 Z [define start of execution]
          P     F [start with accumulator = 0]
 