(49g 50g) Farey Sequence

[John Keith]

This program creates the Farey sequence of order n. It is based on the Python program in the linked Wikipedia page with some optimizations. The program requires the ListExt Library, and must be run in exact mode.

The program returns a list of two lists, the numerators and denominators of the sequence. These are row n of A006842 and A006843 respectively. To get the sequence as a list of ratios, execute EVAL /.

Code:


\<< DUP LSEQ EULER \GSLIST I\->R 1. + \-> n m
  \<< 0 1 DUP2 1 n 2. m
    START \-> a b c d
      \<< c d c d b n + I\->R d I\->R / IP R\->I
c OVER * a - d ROT * b -
      \>>
    NEXT DROP2 DROP2 m 2 * \->LIST m LDIST
  \>>
\>>