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:
TODO: describe the proof