Farey Sequence

While solving this problem, I learned Farey sequence and its definition. There are two interesting properties of this sequence. Les said  Farey sequence F(n), where n is is the biggest denominator in all terms. Then for every successive term a/b, c/d we have:

b*c – a*d = 1 . (1)

And to generate F(n+1) from F(n), we only need to insert mediant of each successive terms, if its denominator is less or equal to n+1. In other words, if F(n+1) has a new term p/q between a/b and c/d,  then:

p = a+c .

q= b+d . (2)

Using above two properties we can easily generate any Farey sequence F(n). However, Wikipedia does not provide the proof of these properties. After couple search I found a blog with very good explanations:

https://sumidiot.wordpress.com/2009/11/03/farey-sequences/

https://sumidiot.wordpress.com/2009/11/05/neighbors-in-farey-sequences/

http://www.ww.ingeniousmathstat.org/sites/default/files/pdf/upload_library/22/Allendoerfer/1982/0025570x.di021121.02p0002y.pdf

TODO: describe the proof

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s