COME ON CODE ON

A blog about programming and more programming.

Farey Sequence/Series

with 2 comments

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 :
Length
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

Advertisements

Written by fR0DDY

March 1, 2009 at 10:04 AM

Posted in Maths, Programming

Tagged with , , , , ,

2 Responses

Subscribe to comments with RSS.

  1. Could you please explain the formula?

    Phan Duy Đức

    January 4, 2014 at 9:33 AM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: