Farey sequence Created 2026-10-07 Updated 2026-11-05
For a positive integer , the Farey sequence is the increasing list of reduced fractions in with denominators at most , including and . For example,Each denominator contributes exactly new interior fractions, because the allowable numerators are precisely those coprime to . Therefore the number of terms is , using the summatory totient function.
For two distinct fractions in the list, their difference is , since the integer is positive. This arithmetic separation, rather than arbitrary real spacing, makes Farey fractions useful in rational approximation. The Stern-Brocot tree organizes the same positive reduced fractions by mediant insertion instead of a denominator cutoff.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 23 5 c Solution Created 2026-10-03 Updated 2026-10-07
Use the distinct reduced fractions with , and , regarded in . The fraction zero appears as ; one is the same circle point and is not added a second time. For two distinct such points, the ordinary difference and its possible wrapped complement are nonzero integer multiples of . HenceThis proves the required separation of the Farey fractions.