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

### Like this:

Like Loading...

## Published by wilsonhongblog

coding saves the world
View all posts by wilsonhongblog