## Farey Sequence/Series

**Farey Sequence** of order **N** is the ascending sequnce of all reduced fractions between **0** and **1** that have denominators **<=N. **For example, the Farey Series of order 4 is

^{0}⁄_{1}, ^{1}⁄_{4}, ^{1}⁄_{3}, ^{1}⁄_{2}, ^{2}⁄_{3}, ^{3}⁄_{4}, ^{1}⁄_{1}

This series can be generated using the following recurrence relation

*x*_{0}=0 *y*_{0}=1

*x*_{1}=1 *y*_{1}=N

*x*_{k+2}= floor((*y*_{k}+N)/*y*_{k+1})*x*_{k+1}– *x*_{k}

*y*_{k+2}= floor((*y*_{k}+N)/*y*_{k+1})*y*_{k+1}– *y*_{k}

The C++ Implementation would look something like this :

x1=0,y1=1,x2=1,y2=N; x=1;y=N; printf("%.0lf/%.0lf, %.0lf/%.0lf",x1,y1,x2,y2); while (y!=1.0) { x=floor((y1+N)/(y2))*x2-x1; y=floor((y1+N)/(y2))*y2-y1; printf(", %.0lf/%.0lf",x,y); x1=x2,x2=x,y1=y2,y2=y; } printf("\n");

Note that the number of terms in the Farey Series is given by :

where phi(m) is the Euler Toteint Function.

Did You Know?

77 x 999 = 777 x 99 and

112 x 112 = 12544 and its back order

211 x 211 = 44521

NJOY!!!

-fR0D

Could you please explain the formula?

Phan Duy ĐứcJanuary 4, 2014 at 9:33 AM

The formula is based on the mediant property described in the below link.

https://en.wikipedia.org/wiki/Farey_series#Farey_neighbours

fR0DDYJanuary 4, 2014 at 12:08 PM