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, 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:  1/'n " has" # 'fractions.',150,'═')
    if oldL>0  then say @;     say    /*display Farey fractions (if +).*/
    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:  1/1  has  2  fractions.═════════════════════════════════════════════════════
0/1 1/1

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

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

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

════════════════════════════════════════════════════Farey sequence for:  1/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:  1/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:  1/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:  1/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:  1/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:  1/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:  1/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:  1/100  has  3045  fractions. ═══════════════════════════════════════════════════

═════════════════════════════════════════════════Farey sequence for:  1/200  has  12233  fractions. ═══════════════════════════════════════════════════

═════════════════════════════════════════════════Farey sequence for:  1/300  has  27399  fractions. ═══════════════════════════════════════════════════

═════════════════════════════════════════════════Farey sequence for:  1/400  has  48679  fractions. ═══════════════════════════════════════════════════

═════════════════════════════════════════════════Farey sequence for:  1/500  has  76117  fractions. ═══════════════════════════════════════════════════

════════════════════════════════════════════════Farey sequence for:  1/600  has  109501  fractions. ═══════════════════════════════════════════════════

════════════════════════════════════════════════Farey sequence for:  1/700  has  149019  fractions. ═══════════════════════════════════════════════════

════════════════════════════════════════════════Farey sequence for:  1/800  has  194751  fractions. ═══════════════════════════════════════════════════

════════════════════════════════════════════════Farey sequence for:  1/900  has  246327  fractions. ═══════════════════════════════════════════════════

════════════════════════════════════════════════Farey sequence for:  1/1000  has  304193  fractions. ═══════════════════════════════════════════════════