COME ON CODE ON

A blog about programming and more programming.

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

01, 14, 13, 12, 23, 34, 11

This series can be generated using the following recurrence relation

x0=0     y0=1
x1=1     y1=N
xk+2= floor((yk+N)/yk+1)xk+1xk
yk+2= floor((yk+N)/yk+1)yk+1yk

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

Written by fR0DDY

March 1, 2009 at 10:04 AM

Posted in Maths, Programming

Tagged with , , , , ,