## Farey Sequence

#### Problem

Starting with F_{1}={0/1, 1/1}, F_{n} is generated by comparing adjacent fractions in F_{n–1}: `a/b` and `c/d`. If `b`+`d`=`n`, then the mediant, (`a`+`c`)/(`b`+`d`), is placed between them. Consider the first six sets:

F_{1}={0/1, 1/1}

F_{2}={0/1, **1/2**, 1/1}

F_{3}={0/1, **1/3**, 1/2, **2/3**, 1/1}

F_{4}={0/1, **1/4**, 1/3, 1/2, 2/3, **3/4**, 1/1}

F_{5}={0/1, **1/5**, 1/4, 1/3, **2/5**, 1/2, **3/5**, 2/3, 3/4, **4/5**, 1/1}

F_{6}={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}

Remarkably, F_{n} represents the ordered list of reduced fraction for which the denominator does not exceed `n`, and is called the Farey sequence.

- What fraction is the immediate predecessor of 2/5 in F
_{100}? - Given that
`a/b`and`c/d`are two consecutive fractions in F_{n}, prove,`bc`–`ad`=1.- when a new fraction of the form, (
`a`+`c`)/(`b`+`d`), is inserted, then`a/b`(`a`+`c`)/(`b`+`d`)`c/d`.

Problem ID: 181 (Oct 2004) Difficulty: 4 Star