Farey sequence

From Fōrmulæ wiki
Jump to: navigation, search

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

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

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:

ExampleCode.png

Task 1

Compute and show the Farey sequence for orders 1 through 11 (inclusive).

FareySequenceOutput1.png

Task 2

Compute and display the number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds.

FareySequenceOutput2.png

Task 3

Show the fractions as n/d (using the solidus [or slash] to separate the numerator from the denominator).

FareySequenceOutput3.png

FareySequenceOutput4.png