mathschallenge.net logo

Farey Sequence

Problem

Starting with F1={0/1, 1/1}, Fn is generated by comparing adjacent fractions in Fn–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:

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, 3/4, 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}

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

  1. What fraction is the immediate predecessor of 2/5 in F100?
  2. Given that a/b and c/d are two consecutive fractions in Fn, prove,
    1. bcad=1.
    2. when a new fraction of the form, (a+c)/(b+d), is inserted, then a/b less than (a+c)/(b+d) less than c/d.
Problem ID: 181 (Oct 2004)     Difficulty: 4 Star

Show Problem & Solution