Farey sequence

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

This page is the answer to the task Farey sequence in the Rosetta Code.

Contents

Description (from Rosetta Code)

 The Farey sequence Fn of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size. The Farey sequence is sometimes incorrectly called a Farey series. Each Farey sequence: Starts with the value 0, denoted by the fraction  Ends with the value 1, denoted by the fraction . The Farey sequences of orders 1 to 5 are:      Tasks Compute and show the Farey sequence for orders 1 through 11 (inclusive). Compute and display the number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds. Show the fractions as n/d (using the solidus [or slash] to separate the numerator from the denominator). See also OEIS sequence A006842 numerators of Farey series of order 1, 2, ··· OEIS sequence A006843 denominators of Farey series of order 1, 2, ··· OEIS sequence A005728 number of fractions in Farey series of order n. MathWorld entry Farey sequence

Program

The same program when the flowchart package visualization is selected. Click/tap to enlarge

Using the algorithm to calculate the successive terms of the sequence, shown here: