The ascending (finite) sequence of reduced fractions between 0 and 1 with denominator <= n is known as Fn, the Farey sequence of order n.

Examples:

F1 = 0/1, 1/1
F2 = 0/1, 1/2, 1/1
F3 = 0/1, 1/3, 1/2, 2/3, 1/1
F4 = 0/1, 1/4, 1/3, 1/2, 2/3, 1/1
F5 = 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
F6 = 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1
F7 = 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1
...
Farey sequences show "simplest" decompositions of the interval [0,1]. They turn out to have many beautiful properties. Using them, the theory of continued fractions has a rather elegant formulation.
The Farey sequence is most easily generated through the use of what is known as the Stern Berchot method.

This method centers around the incorrect method of adding fractions that many grade school, high school, and even some college kids employ.

(a/b) + (c/d) = (a+c)/(b+d)

Starting with the F1 case of 0/1 and 1/1, one simply adds two adjacent members of the sequence to generate the next level. An example is in order:

for n=1: 0/1, 1/1
n=2: 0/1, 0+1/1+1 (1/2), 1/1
n=3: 0/1, 0+1/1+2 (1/3), 1/2, 1+1/1+2 (2/3), 1/1
etc

If you're going to generate the sequence in a program, it's best to use two list iterators, one behind the other, to generate the next level.

Log in or register to write something here or to contact authors.