Farey sequence

Farey sequence

(sometimes incorrectly called a Farey series.)

definition

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

Each Farey sequence starts with value 0, denoted by the fraction ${\frac {0}{1}}$ and ends with the value 1, denoted by the fraction ${\frac {1}{1}}$ .

The Farey sequences of orders 1 to 5 are:

F₁ =

{\frac {0}{1}},{\frac {1}{1}}

F₂ =

{\frac {0}{1}},{\frac {1}{2}},{\frac {1}{1}}

F₃ =

{\frac {0}{1}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {1}{1}}

F₄ =

{\frac {0}{1}},{\frac {1}{4}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {3}{4}},{\frac {1}{1}}

F₅ =

{\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 requirements

compute and show the Farey sequence for order 1 through 11 (inclusive).
compute and display the number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds.

see also

sequence A006842 numerators of Farey series of order 1, 2, ··· on OEIS, The On-line Encyclopedia of Integer Sequences (R).
sequence A006843 denominators of Farey series of order 1, 2, ··· on OEIS, The On-line Encyclopedia of Integer Sequences (R).
sequence A005728 number of fractions in Farey series of order n. on OEIS, The On-line Encyclopedia of Integer Sequences (R).
entry Farey sequence on Wolfram Mathworld (TM).
Wiki Farey sequence in Wikipedia.

REXX

<lang rexx>/*REXX program computes & shows a Farey sequence (or the # of fractions)*/ parse arg L H I . /*get optional values from C.L. */ if L== then L=5 /*L not specified? Use default.*/ oldL=L /*original L (negativity=noshow)*/ L=abs(L) /*but ··· use |L| for all else.*/ if H== then H=L /*H not specified? Use default.*/ if I== then I=1 /*I " " " " */

    do n=L  to  H  by I               /*process range (could be only 1)*/
    @=fareyF(n);    #=' 'words(@)" "  /*go ye forth & compute Farey #s.*/
    say center('Farey sequence for order '   n   " has"   #   'fractions.', 150, '═')
    if oldL<0  then iterate           /*don't show Farey fractions if -*/
    say @;          say               /*show Farey fractions+blank line*/
    end   /*n*/                       /* [↑] build/show Farey fractions*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────FAREYF subroutine───────────────────*/ fareyf: procedure; parse arg x; n.1=0; d.1=1; n.2=1; d.2=x /*kit parts.*/ $=n.1'/'d.1 n.2"/"d.2 /*a starter kit for the Farey seq*/

                                      /* [↓]  now, build on the starter*/
         do j=1;  y=j+1;  z=j+2       /*construct from thirds on "up". */
         n.z=((d.j+x)%d.y)*n.y-n.j    /*    "     fraction numerator.  */
         d.z=((d.j+x)%d.y)*d.y-d.j    /*    "         "    denominator.*/
         if n.z>x  then leave         /*Should construction be stopped?*/
         $=$ n.z'/'d.z                /*Heck no, add this to party mix.*/
         end   /*j*/                  /* [↑]  construct the Farey seq. */

return $ /*return with the fractions. */</lang> output when using the following for input: 1 11

═══════════════════════════════════════════════════Farey sequence for order  1  has  2  fractions.════════════════════════════════════════════════════
0/1 1/1

═══════════════════════════════════════════════════Farey sequence for order  2  has  3  fractions.════════════════════════════════════════════════════
0/1 1/2 1/1

═══════════════════════════════════════════════════Farey sequence for order  3  has  5  fractions.════════════════════════════════════════════════════
0/1 1/3 1/2 2/3 1/1

═══════════════════════════════════════════════════Farey sequence for order  4  has  7  fractions.════════════════════════════════════════════════════
0/1 1/4 1/3 1/2 2/3 3/4 1/1

═══════════════════════════════════════════════════Farey sequence for order  5  has  11  fractions.═══════════════════════════════════════════════════
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

═══════════════════════════════════════════════════Farey sequence for order  6  has  13  fractions.═══════════════════════════════════════════════════
0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1

═══════════════════════════════════════════════════Farey sequence for order  7  has  19  fractions.═══════════════════════════════════════════════════
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 for order  8  has  23  fractions.═══════════════════════════════════════════════════
0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1

═══════════════════════════════════════════════════Farey sequence for order  9  has  29  fractions.═══════════════════════════════════════════════════
0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1

══════════════════════════════════════════════════Farey sequence for order  10  has  33  fractions.═══════════════════════════════════════════════════
0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1

══════════════════════════════════════════════════Farey sequence for order  11  has  43  fractions.═══════════════════════════════════════════════════
0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

output when using the following for input: -100 1000 100

═════════════════════════════════════════════════Farey sequence for order  100  has  3045  fractions.═════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  200  has  12233  fractions.═════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  300  has  27399  fractions.═════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  400  has  48679  fractions.═════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  500  has  76117  fractions.═════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  600  has  109501  fractions.════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  700  has  149019  fractions.════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  800  has  194751  fractions.════════════════════════════════════════════════
════════════════════════════════════════════════Farey sequence for order  900  has  246327  fractions.════════════════════════════════════════════════
═══════════════════════════════════════════════Farey sequence for order 10000  has  304193  fractions.════════════════════════════════════════════════