Farey sequence: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:35, 18 January 2021

The Farey sequence F_n 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 (zero), denoted by the fraction ${\frac {0}{1}}$
ends with the value 1 (unity), denoted by the fraction ${\frac {1}{1}}$ .

The Farey sequences of orders 1 to 5 are:

{\bf {\it {F}}}_{1}={\frac {0}{1}},{\frac {1}{1}}

{\bf {\it {F}}}_{2}={\frac {0}{1}},{\frac {1}{2}},{\frac {1}{1}}

{\bf {\it {F}}}_{3}={\frac {0}{1}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {1}{1}}

{\bf {\it {F}}}_{4}={\frac {0}{1}},{\frac {1}{4}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {3}{4}},{\frac {1}{1}}

{\bf {\it {F}}}_{5}={\frac {0}{1}},{\frac {1}{5}},{\frac {1}{4}},{\frac {1}{3}},{\frac {2}{5}},{\frac {1}{2}},{\frac {3}{5}},{\frac {2}{3}},{\frac {3}{4}},{\frac {4}{5}},{\frac {1}{1}}

Task

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).

The length (the number of fractions) of a Farey sequence asymptotically approaches:

3 × n² ÷

\pi

²

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
Wikipedia entry Farey sequence

11l

Translation of: Lua

<lang 11l>F farey(n)

  V a = 0
  V b = 1
  V c = 1
  V d = n
  V far = ‘0/1 ’
  V farn = 1
  L c <= n
     V k = (n + b) I/ d
     (a, b, c, d) = (c, d, k * c - a, k * d - b)
     far ‘’= a‘/’b‘ ’
     farn++
  R (far, farn)

L(i) 1..11

  print(i‘: ’farey(i)[0])

L(i) (100..1000).step(100)

  print(i‘: ’farey(i)[1]‘ items’)</lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045 items
200: 12233 items
300: 27399 items
400: 48679 items
500: 76117 items
600: 109501 items
700: 149019 items
800: 194751 items
900: 246327 items
1000: 304193 items

APL

<lang APL> farey←{{⍵[⍋⍵]}∪∊{(0,⍳⍵)÷⍵}¨⍳⍵} fract←{1∧(0(⍵=0)+⊂⍵)*1 ¯1} print←{{(⍕⍺),'/',(⍕⍵),' '}⌿↑fract farey ⍵} </lang> Note that this is a brute-force algorithm, not the sequential one given on Wikipedia. Basically, given n this one generates and then sorts the set

{ p/q | p,q integers, 0 <= p <= q, 1 <= q <= n }

.

Output:

      {⍵⍪(⊂'¯¯¯¯¯')⍪⍉↑print¨⍵}⍳11    ⍝ Sequences
     1      2      3      4      5      6      7      8      9     10      11 
 ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯  ¯¯¯¯¯   ¯¯¯¯¯ 
  0/1    0/1    0/1    0/1    0/1    0/1    0/1    0/1    0/1    0/1     0/1  
  1/1    1/2    1/3    1/4    1/5    1/6    1/7    1/8    1/9   1/10    1/11  
         1/1    1/2    1/3    1/4    1/5    1/6    1/7    1/8    1/9    1/10  
                2/3    1/2    1/3    1/4    1/5    1/6    1/7    1/8     1/9  
                1/1    2/3    2/5    1/3    1/4    1/5    1/6    1/7     1/8  
                       3/4    1/2    2/5    2/7    1/4    1/5    1/6     1/7  
                       1/1    3/5    1/2    1/3    2/7    2/9    1/5     1/6  
                              2/3    3/5    2/5    1/3    1/4    2/9    2/11  
                              3/4    2/3    3/7    3/8    2/7    1/4     1/5  
                              4/5    3/4    1/2    2/5    1/3    2/7     2/9  
                              1/1    4/5    4/7    3/7    3/8   3/10     1/4  
                                     5/6    3/5    1/2    2/5    1/3    3/11  
                                     1/1    2/3    4/7    3/7    3/8     2/7  
                                            5/7    3/5    4/9    2/5    3/10  
                                            3/4    5/8    1/2    3/7     1/3  
                                            4/5    2/3    5/9    4/9    4/11  
                                            5/6    5/7    4/7    1/2     3/8  
                                            6/7    3/4    3/5    5/9     2/5  
                                            1/1    4/5    5/8    4/7     3/7  
                                                   5/6    2/3    3/5     4/9  
                                                   6/7    5/7    5/8    5/11  
                                                   7/8    3/4    2/3     1/2  
                                                   1/1    7/9   7/10    6/11  
                                                          4/5    5/7     5/9  
                                                          5/6    3/4     4/7  
                                                          6/7    7/9     3/5  
                                                          7/8    4/5     5/8  
                                                          8/9    5/6    7/11  
                                                          1/1    6/7     2/3  
                                                                 7/8    7/10  
                                                                 8/9     5/7  
                                                                9/10    8/11  
                                                                 1/1     3/4  
                                                                         7/9  
                                                                         4/5  
                                                                        9/11  
                                                                         5/6  
                                                                         6/7  
                                                                         7/8  
                                                                         8/9  
                                                                        9/10  
                                                                       10/11  
                                                                         1/1  

      {⍵,'|',[1.5]≢∘farey¨⍵}100×⍳10    ⍝ Sequence lengths
 100 |   3045
 200 |  12233
 300 |  27399
 400 |  48679
 500 |  76117
 600 | 109501
 700 | 149019
 800 | 194751
 900 | 246327
1000 | 304193

AWK

syntax: GAWK -f FAREY_SEQUENCE.AWK

BEGIN {

   for (i=1; i<=11; i++) {
     farey(i); printf("\n")
   }
   for (i=100; i<=1000; i+=100) {
     printf(" %d items\n",farey(i))
   }
   exit(0)

} function farey(n, a,aa,b,bb,c,cc,d,dd,items,k) {

   a = 0; b = 1; c = 1; d = n
   printf("%d:",n)
   if (n <= 11) {
     printf(" %d/%d",a,b)
   }
   while (c <= n) {
     k = int((n+b)/d)
     aa = c; bb = d; cc = k*c-a; dd = k*d-b
     a = aa; b = bb; c = cc; d = dd
     items++
     if (n <= 11) {
       printf(" %d/%d",a,b)
     }
   }
   return(1+items)

} </lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045 items
200: 12233 items
300: 27399 items
400: 48679 items
500: 76117 items
600: 109501 items
700: 149019 items
800: 194751 items
900: 246327 items
1000: 304193 items

C

<lang c>#include <stdio.h>

include <stdlib.h>
include <string.h>

void farey(int n) { typedef struct { int d, n; } frac; frac f1 = {0, 1}, f2 = {1, n}, t; int k;

printf("%d/%d %d/%d", 0, 1, 1, n); while (f2.n > 1) { k = (n + f1.n) / f2.n; t = f1, f1 = f2, f2 = (frac) { f2.d * k - t.d, f2.n * k - t.n }; printf(" %d/%d", f2.d, f2.n); }

putchar('\n'); }

typedef unsigned long long ull; ull *cache; size_t ccap;

ull farey_len(int n) { if (n >= ccap) { size_t old = ccap; if (!ccap) ccap = 16; while (ccap <= n) ccap *= 2; cache = realloc(cache, sizeof(ull) * ccap); memset(cache + old, 0, sizeof(ull) * (ccap - old)); } else if (cache[n]) return cache[n];

ull len = (ull)n*(n + 3) / 2; int p, q = 0; for (p = 2; p <= n; p = q) { q = n/(n/p) + 1; len -= farey_len(n/p) * (q - p); }

cache[n] = len; return len; }

int main(void) { int n; for (n = 1; n <= 11; n++) { printf("%d: ", n); farey(n); }

for (n = 100; n <= 1000; n += 100) printf("%d: %llu items\n", n, farey_len(n));

n = 10000000; printf("\n%d: %llu items\n", n, farey_len(n)); return 0; }</lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045 items
200: 12233 items
300: 27399 items
400: 48679 items
500: 76117 items
600: 109501 items
700: 149019 items
800: 194751 items
900: 246327 items
1000: 304193 items

10000000: 30396356427243 items

C#

Works with: C sharp version 7

Translation of: Java

<lang csharp>using System; using System.Collections.Generic; using System.Linq;

public static class FareySequence {

   public static void Main() {
       for (int i = 1; i <= 11; i++) {
           Console.WriteLine($"F{i}: " + string.Join(", ", Generate(i).Select(f => $"{f.num}/{f.den}")));
       }
       for (int i = 100; i <= 1000; i+=100) {
           Console.WriteLine($"F{i} has {Generate(i).Count()} terms.");
       }
   }

   public static IEnumerable<(int num, int den)> Generate(int i) {
       var comparer = Comparer<(int n, int d)>.Create((a, b) => (a.n * b.d).CompareTo(a.d * b.n));
       var seq = new SortedSet<(int n, int d)>(comparer);
       for (int d = 1; d <= i; d++) {
           for (int n = 0; n <= d; n++) {
               seq.Add((n, d));
           }
       }
       return seq;
   }

}</lang>

Output:

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
F7: 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1
F8: 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1
F9: 0/1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1/1
F10: 0/1, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1/1
F11: 0/1, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1/1
F100 has 3045 terms.
F200 has 12233 terms.
F300 has 27399 terms.
F400 has 48679 terms.
F500 has 76117 terms.
F600 has 109501 terms.
F700 has 149019 terms.
F800 has 194751 terms.
F900 has 246327 terms.
F1000 has 304193 terms.

C++

Object-based programming

<lang cpp>#include <iostream>

struct fraction {

   fraction(int n, int d) : numerator(n), denominator(d) {}
   int numerator;
   int denominator;

};

std::ostream& operator<<(std::ostream& out, const fraction& f) {

   out << f.numerator << '/' << f.denominator;
   return out;

}

class farey_sequence { public:

   explicit farey_sequence(int n) : n_(n), a_(0), b_(1), c_(1), d_(n) {}
   fraction next() {
       // See https://en.wikipedia.org/wiki/Farey_sequence#Next_term
       fraction result(a_, b_);
       int k = (n_ + b_)/d_;
       int next_c = k * c_ - a_;
       int next_d = k * d_ - b_;
       a_ = c_;
       b_ = d_;
       c_ = next_c;
       d_ = next_d;
       return result;
   }
   bool has_next() const { return a_ <= n_; }

private:

   int n_, a_, b_, c_, d_;

};

int main() {

   for (int n = 1; n <= 11; ++n) {
       farey_sequence seq(n);
       std::cout << n << ": " << seq.next();
       while (seq.has_next())
           std::cout << ' ' << seq.next();
       std::cout << '\n';
   }
   for (int n = 100; n <= 1000; n += 100) {
       int count = 0;
       for (farey_sequence seq(n); seq.has_next(); seq.next())
           ++count;
       std::cout << n << ": " << count << '\n';
   }
   return 0;

}</lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045 items
200: 12233 items
300: 27399 items
400: 48679 items
500: 76117 items
600: 109501 items
700: 149019 items
800: 194751 items
900: 246327 items
1000: 304193 items

Object-oriented programming

Works with: C++17

<lang cpp>#include <iostream>

include <list>
include <utility>

struct farey_sequence: public std::list<std::pair<uint, uint>> {

   explicit farey_sequence(uint n) : order(n) {
       push_back(std::pair(0, 1));
       uint a = 0, b = 1, c = 1, d = n;
       while (c <= n) {
           const uint k = (n + b) / d;
           const uint next_c = k * c - a;
           const uint next_d = k * d - b;
           a = c;
           b = d;
           c = next_c;
           d = next_d;
           push_back(std::pair(a, b));
       }
   }

   const uint order;

};

std::ostream& operator<<(std::ostream &out, const farey_sequence &s) {

   out << s.order << ":";
   for (const auto &f : s)
       out << ' ' << f.first << '/' << f.second;
   return out;

}

int main() {

   for (uint i = 1u; i <= 11u; ++i)
       std::cout << farey_sequence(i) << std::endl;
   for (uint i = 100u; i <= 1000u; i += 100u) {
       const auto s = farey_sequence(i);
       std::cout << s.order << ": " << s.size() << " items" << std::endl;
   }

   return EXIT_SUCCESS;

}</lang>

Common Lisp

The common lisp version of the code is taken from the scala version with some modifications: <lang lisp>(defun farey (n)

 (labels ((helper (begin end)

(let ((med (/ (+ (numerator begin) (numerator end)) (+ (denominator begin) (denominator end))))) (if (<= (denominator med) n) (append (helper begin med) (list med) (helper med end))))))

     (append (list 0) (helper 0 1) (list 1))))

Force printing of integers in X/1 format

(defun print-ratio (stream object &optional colonp at-sign-p)

 (format stream "~d/~d" (numerator object) (denominator object)))

(loop for i from 1 to 11 do

    (format t "~a: ~{~/print-ratio/ ~}~%" i (farey i)))

(loop for i from 100 to 1001 by 100 do

    (format t "Farey sequence of order ~a has ~a terms.~%" i (length (farey i))))

</lang>

Output:

1: 0/1 1/1 
2: 0/1 1/2 1/1 
3: 0/1 1/3 1/2 2/3 1/1 
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1 
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 
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 
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1 
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1 
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1 

Farey sequence of order 100 has 3045 terms.
Farey sequence of order 200 has 12233 terms.
Farey sequence of order 300 has 27399 terms.
Farey sequence of order 400 has 48679 terms.
Farey sequence of order 500 has 76117 terms.
Farey sequence of order 600 has 109501 terms.
Farey sequence of order 700 has 149019 terms.
Farey sequence of order 800 has 194751 terms.
Farey sequence of order 900 has 246327 terms.
Farey sequence of order 1000 has 304193 terms.

Crystal

Translation of: the function from Lua, the output from Ruby.

Slow Version <lang ruby>require "big"

def farey(n)

   a, b, c, d = 0, 1, 1, n
   fracs = [] of BigRational
   fracs << BigRational.new(0,1)
   while c <= n
       k = (n + b) // d
       a, b, c, d = c, d, k * c - a, k * d - b
       fracs << BigRational.new(a,b)
   end
   fracs.uniq.sort

end

puts "Farey sequence for order 1 through 11 (inclusive):" (1..11).each do |n|

 puts "F(#{n}): 0/1 #{farey(n)[1..-2].join(" ")} 1/1"

end

puts "Number of fractions in the Farey sequence:" (100..1000).step(100) do |i|

 puts "F(%4d) =%7d" % [i, farey(i).size]

end </lang>

Translation of: the function from Python, the output from Ruby.

Fast Version <lang ruby>require "big"

def farey(n, length = false)

 a = [] of BigRational
 if length
   (n*(n+3))//2 - (2..n).sum{ |k| farey(n//k, true).as(Int32) }
 else
   (1..n).each{ |k| (0..k).each{ |m| a << BigRational.new(m,k) } }; a.uniq.sort
 end

end

puts "Farey sequence for order 1 through 11 (inclusive):" (1..11).each do |n|

 puts "F(#{n}): 0/1 #{farey(n).as(Array(BigRational))[1..-2].join(" ")} 1/1"

end

puts "Number of fractions in the Farey sequence:" (100..1000).step(100) do |i|

 puts "F(%4d) =%7d" % [i, farey(i, true)]

end </lang>

Output:

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
F(7): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
F(8): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
F(9): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
Number of fractions in the Farey sequence:
F( 100) =   3045
F( 200) =  12233
F( 300) =  27399
F( 400) =  48679
F( 500) =  76117
F( 600) = 109501
F( 700) = 149019
F( 800) = 194751
F( 900) = 246327
F(1000) = 304193

D

This example is in need of improvement:

The output for the first and last term (as per the task's requirement)

is to show the first term as 0/1,

and to show the last term as 1/1.

This imports the module from the Arithmetic/Rational task. <lang d>import std.stdio, std.algorithm, std.range, arithmetic_rational;

auto farey(in int n) pure nothrow @safe {

   return rational(0, 1).only.chain(
           iota(1, n + 1)
           .map!(k => iota(1, k + 1).map!(m => rational(m, k)))
           .join.sort().uniq);

}

void main() @safe {

   writefln("Farey sequence for order 1 through 11:\n%(%s\n%)",
            iota(1, 12).map!farey);
   writeln("\nFarey sequence fractions, 100 to 1000 by hundreds:\n",
           iota(100, 1_001, 100).map!(i => i.farey.walkLength));

}</lang>

Output:

Farey sequence for order 1 through 11:
[0, 1]
[0, 1/2, 1]
[0, 1/3, 1/2, 2/3, 1]
[0, 1/4, 1/3, 1/2, 2/3, 3/4, 1]
[0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1]
[0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1]
[0, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1]
[0, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1]
[0, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1]
[0, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1]
[0, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1]

Farey sequence fractions, 100 to 1000 by hundreds:
[3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193]

Alternative Version

This is as fast as the C entry (total run-time is 0.20 seconds).

Translation of: C

<lang d>import core.stdc.stdio: printf, putchar;

void farey(in uint n) nothrow @nogc {

   static struct Frac { uint d, n; }

   Frac f1 = { 0, 1 }, f2 = { 1, n };

   printf("%u/%u %u/%u", 0, 1, 1, n);
   while (f2.n > 1) {
       immutable k = (n + f1.n) / f2.n;
       immutable aux = f1;
       f1 = f2;
       f2 = Frac(f2.d * k - aux.d, f2.n * k - aux.n);
       printf(" %u/%u", f2.d, f2.n);
   }

   putchar('\n');

}

ulong fareyLength(in uint n, ref ulong[] cache) pure nothrow @safe {

   if (n >= cache.length) {
       auto newLen = cache.length;
       if (newLen == 0)
           newLen = 16;
       while (newLen <= n)
           newLen *= 2;
       cache.length = newLen;
   } else if (cache[n])
       return cache[n];

   ulong len = ulong(n) * (n + 3) / 2;
   for (uint p = 2, q = 0; p <= n; p = q) {
       q = n / (n / p) + 1;
       len -= fareyLength(n / p, cache) * (q - p);
   }

   cache[n] = len;
   return len;

}

void main() nothrow {

   foreach (immutable uint n; 1 .. 12) {
       printf("%u: ", n);
       n.farey;
   }

   ulong[] cache;
   for (uint n = 100; n <= 1_000; n += 100)
       printf("%u: %llu items\n", n, fareyLength(n, cache));

   immutable uint n = 10_000_000;
   printf("\n%u: %llu items\n", n, fareyLength(n, cache));

}</lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045 items
200: 12233 items
300: 27399 items
400: 48679 items
500: 76117 items
600: 109501 items
700: 149019 items
800: 194751 items
900: 246327 items
1000: 304193 items

10000000: 30396356427243 items

EchoLisp

This example is incorrect. Please fix the code and remove this message.

Details:

The output for the first and last term (as per the task's requirement)

is to show the first term as 0/1,

and to show the last term as 1/1.

<lang scheme> (define distinct-divisors (compose make-set prime-factors))

euler totient

Φ: n / product(p_i) * product (p_i - 1)
# of divisors <= n

(define (Φ n) (let ((pdiv (distinct-divisors n))) (/ (* n (for/product ((p pdiv)) (1- p))) (for/product ((p pdiv)) p))))

farey-sequence length |Fn| = 1 + sigma (m=1..) Φ(m)

(define ( F-length n) (1+ (for/sum ((m (1+ n))) (Φ m))))

farey sequence apply the definition O(n^2)

(define (Farey N) (set! N (1+ N)) (make-set (for*/list ((n N) (d (in-range n N))) (rational n d))))

</lang>

Output:

<lang scheme> (for ((n (in-range 1 12))) ( printf "F(%d) %s" n (Farey n))) F(1) { 0 1 } F(2) { 0 1/2 1 } F(3) { 0 1/3 1/2 2/3 1 } F(4) { 0 1/4 1/3 1/2 2/3 3/4 1 } F(5) { 0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1 } F(6) { 0 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1 } F(7) { 0 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1 } F(8) { 0 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1 } F(9) { 0 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1 } F(10) { 0 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1 } F(11) { 0 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1 }

(for (( n (in-range 100 1100 100))) (printf "|F(%d)| = %d" n (F-length n))) |F(100)| = 3045 |F(200)| = 12233 |F(300)| = 27399 |F(400)| = 48679 |F(500)| = 76117 |F(600)| = 109501 |F(700)| = 149019 |F(800)| = 194751 |F(900)| = 246327 |F(1000)| = 304193

(for (( n '(10_000 100_000))) (printf "|F(%d)| = %d" n (F-length n))) |F(10000)| = 30397487 |F(100000)| = 3039650755 </lang>

EDSAC order code

Print terms

Each Farey sequence is generated term by term, by the method described in Wikipedia. The EDSAC did not have built-in division; since the numbers in this program are very small, division is done by repeated subtraction.

The code is slightly simplified by adding a formal term -1/0 before the first term 0/1. The second term can then be included in the calculation loop. <lang edsac>

[Farey sequence for Rosetta Code website.
 EDSAC program, Initial Orders 2.
 Prints Farey sequences up to order 11
 (or other limit determined by a simple edit).]

[Modification of library subroutine P6.
 Prints number (absolute value <= 65535)
 passed in 0F, without leading spaces.
 41 locations.]
         T 56 K
 GKA3FT35@SFG11@UFS40@E10@O40@T4FE35@O@T4F
 H38@VFT4DA13@TFH39@S16@T1FV4DU4DAFG36@TFTF
 O5FA4DF4FS4FL4FT4DA1FS13@G19@EFSFE30@J995FJFPD

         T 100 K
         G     K
 [Maximum order to be printed. For convenience, entered as
 an address, not an integer, e.g. 'P 11 F' not 'P 5 D'.]
   [0]   P  11 F [<--- edit here]
 [Other constants]
   [1]   P     D [1]
   [2]   #     F [figure shift]
   [3]   X     F [slash]
   [4]   !     F [space]
   [5]   @     F [carriage return]
   [6]   &     F [line feed]
   [7]   K4096 F [teleprinter null]
 [Variables]
   [8]   P     F [n, order of current Farey sequence]
   [9]   P     F [maximum n + 1, as integer]
         [a/b and c/d are consecutive terms of the Farey sequence]
  [10]   P     F [a]
  [11]   P     F [b]
  [12]   P     F [c]
  [13]   P     F [d]
  [14]   P     F [t, temporary store]

         [Subroutine to print c/d]
  [15]   A   3 F [plant link for return]
         T  26 @
         A  12 @ [load c]
         T     F [to 0F for printing]
  [19]   A  19 @ [for subroutine return]
         G  56 F [print c]
         O   3 @ [print '/']
         A  13 @ [load d]
         T     F [to 0F for printing]
  [24]   A  24 @ [for subroutine return]
         G  56 F [print d]
  [26]   E     F [return]

          [Main routine.
          Enter with accumulator = 0.]
  [27]   O   2 @ [set teleprinter to figures]
         A     @ [max order as address]
         R     D [shift 1 right to make integer]
         A   1 @ [add 1]
         T   9 @ [save for comparison]
         A   1 @ [start with order 1]
         [Here with next order (n) in the accumulator]
  [33]   S   9 @ [subtract (max order) + 1]
         E  84 @ [exit if over maximum]
         A   9 @ [restore after test]
         T   8 @ [store]
         [Prefix the Farey sequence with a formal term -1/0.
          The second term is calculated from this and the first term.]
         S   1 @ [acc := -1]
         T  10 @ [a := -1]
         T  11 @ [b := 0]
         T  12 @ [c := 0]
         A   1 @ [d := 1]
         T  13 @
         A  43 @ [for subroutine return]
         G  15 @ [call subroutine to print c/d]

         [Calculate next term; basically same as Wikipedia method]
  [45]   T     F [clear acc]
         A  10 @ [t := a]
         T  14 @
         A  12 @ [a := c;]
         T  10 @
         S  14 @ [c := -t]
         T  12 @
         A  11 @ [t := b]
         T  14 @
         A  13 @ [b := d]
         T  11 @
         S  14 @ [d := -t]
         T  13 @
         A   8 @ [t := n + t]
         A  14 @ 
         T  14 @
         [Inner loop, get t div b by repeated subtraction]
  [61]   A  14 @ [t := t - b]
         S  11 @
         G  72 @ [jump out when t < 0]
         T  14 @
         A  12 @ [c := c + a]
         A  10 @
         T  12 @
         A  13 @ [d := d + b]
         A  11 @ 
         T  13 @
         E  61 @ [loop back (always, since acc = 0)]
         [End of inner loop, print c/d preceded by space]
  [72]   O   4 @ 
         T     F
  [74]   A  74 @ [for subroutine return]
         G  15 @ [call subroutine to print c/d]
         A   1 @ [form 1 - d, to test for d = 1]
         S  13 @
         G  45 @ [if d > 1, loop for next term]
         O   5 @ [else print end of line (CR LF)]
         O   6 @

         [Next Farey series.]
         A   8 @ [load order]
         A   1 @ [add 1]
         E  33 @ [loop back]

         [Here when finished]
  [84]   O   7 @ [output null to flush teleprinter buffer]
         Z     F [stop]
         E  27 Z [define start of execution]
         P     F [start with accumulator = 0]

</lang>

Output:

0/1 1/1
0/1 1/2 1/1
0/1 1/3 1/2 2/3 1/1
0/1 1/4 1/3 1/2 2/3 3/4 1/1
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

Count terms

Counts the terms by summing Euler's totient function. <lang edsac>

[Farey sequence for Rosetta Code website.
 Get number of terms by using Euler's totient function.
 EDSAC program, Initial Orders 2.]

[Euler's totient function for each n = 1..1000 is calculated here as follows.
 A wheel is defined for each prime p < sqrt(1000), i.e. for p <= 31.
 When n = 0, the wheels are all 0. When n is incremented:
 (i)  the totient is initialized to n
 (ii) the wheel for each prime p is incremented modulo p.
 A prime p therefore divides n iff the wheel for p is 0. In this case:
 (1) the totient is multiplied by (1 - 1/p)
 (2) n is reduced by dividing it by p as many times as possible.
 When all primes p have been tested, the reduced n must be either:
 (a) 1, in which case the totient is finished; or
 (b) a prime q > 31, in which case the totient is multiplied by (1 - 1/q).]

[Library subroutine M3, prints header, terminated by blank row of tape.]
 PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
     *!!!!!ORDER!!!!!TERMS@&#..
       [PZ]
           T   56 K
[Library subroutine P7, prints double-word integer > 0.
 10 characters, right justified, padded left with spaces.
 Closed, even; 35 storage locations; working position 4D.]
 GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSF
 L4FT4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@

[Subroutine (not from library) for integer short division.
 Input:  dividend at 4F, divisor at 6F
 Output: remainder at 4F, quotient at 6F
 Working location 0D. 37 locations.]
           T  100 K
 GKA3FT34@A6FUFT35@A4FRDS35@G13@T1FA35@LDE4@T1FT6FA4FS35@G22@
 T4FA6FA36@T6FT1FAFS35@E34@T1FA35@RDT35@A6FLDT6FE15@EFPFPD

 [Put address of primes at 53.
 Primes are therefore referred to by code letter B.]
           T   53 K
           P  160 F
           T  160 K
           P   11 F  [number of primes (as address)]
 P1FP1DP2DP3DP5DP6DP8DP9DP11DP14DP15D

[Put address of wheels at 54.
 Wheels are therefore referred to by code letter C.
 Number of wheels = number of primes, at the moment 11]
           T   54 K
           P  180 F

 [Main routine]
           T  200 K
           G      K
 [Long variable]
     [0]   P F  P F [sum of Euler's totient function over all n]
 [Short variables]
     [2]   P      F [n = order of Farey sequence]
     [3]   P      F [reduced n, as prime factors are taken out]
     [4]   P      F [partial totient; initially n, finally Euler's phi(n)]
     [5]   P      F [current prime p]
     [6]   P      F [residue of n by prime p]
     [7]   P      F [negative counter for steps]
     [8]   P      F [negative counter within step]
     [9]   P      F [negative counter for primes]
[Short constants]
    [10]   P      D [1]
    [11]   P  100 F [step, as an address (for convenience)]
    [12]   P   10 F [number of steps, as an address]
    [13]   #      F [figure shift]
    [14]   @      F [carriage return]
    [15]   &      F [line feed]
    [16]   K 4096 F [teleprinter null]
    [17]   A      C [order to read first wheel]
    [18]   T      C [order to write first wheel]
    [19]   A    1 B [order to read first prime]

          [Subroutine to multiply partial totient by (1 - 1/p)]
    [20]   A    3 F
           T   31 @
           A    4 @ [load partial totient]
           T    4 F [to dividend]
           A    5 @ [load prime p]
           T    6 F [to divisor]
    [26]   A   26 @ [for return from next]
           G  100 F [call division routine]
           A    4 @ [partial totient again]
           S    6 F [subtract quotient]
           T    4 @ [update partial totient]
    [31]   E      F [exit with acc = 0]

          [Enter with accumulator = 0]
          [Reset all wheels to 0, working from 31 down to 2.]
    [32]   A      B [load number of wheels]
           S    2 F [dec by 1]
    [34]   A   18 @ [make order 'T m C' for address m]
           T   36 @ [plant order]
    [36]   T      C [reset this wheel]
           A   36 @ [get order again]
           S    2 F [dec address by 1]
           S   18 @ [compare with order for first wheel]
           E   34 @ [loop back till done]
          [Initialize sum to 1]
           T      F [clear acc]
           T     #@ [clear sum (both words + sandwich bit)]
           A   10 @ [load 1 (single word)]
           T      @ [to sum (low word)]
           T    2 @ [order of Farey sequence := 0]
           S   12 @ [load negative number of steps (typically -10)]
          [Here acc = negative step count]
    [47]   T    7 @ [update negative step count]
           S   11 @ [load negative step size (typically -100)]
          [Here acc = negative count within a step]
    [49]   T    8 @
           A    2 @ [inc n]
           A   10 @
           U    3 @ [initialize reduced n := n]
           U    4 @ [initialize partial totient := n]
           T    2 @ [update n]

          [Loop through primes p. Inc wheel for prime p by 1 mod p.
           If wheel = 0, then p divides n.
           If so, update partial totient and reduced n.]
           S      B
           T    9 @ [initialize count]
           A   19 @ [order to read first prime]
           T   64 @ [plant in code]
           A   17 @ [order to read first wheel]
           T   66 @ [plant in code]
           A   18 @ [order to write first wheel]
           T   88 @ [plant in code]
    [63]   T      F
    [64]   A      F [load prime]
           T    5 @ [store]
    [66]   A      C [read wheel (residue of n mod p)]
           A   10 @ [inc]
           U    6 @ [store locally]
           S    5 @ [reached p yet?]
           G   86 @ [skip if not]

          [Here if p divides n.
           Need to multiply partial totient by (1 - 1/p)
           and divide reduced n by highest possible power of p.]
           T      F [acc := 0]
           T    6 @ [wrap residue from p to 0]
          [Update partial totient, multiply by (1 - 1/p)]
    [73]   A   73 @ [for return from next]
           G   20 @ [call subroutine]
          [Divide reduced n by p as many times as possible
          (it must be divisible by p at least once)]
    [75]   A    3 @ [load reduced n]
           T    4 F [to dividend]
           A    5 @ [load prime p]
           T    6 F [to divisor]
    [79]   A   79 @ [for return]
           G  100 F [call division routine; clears acc]
           S    4 F [load negative of remainder]
           G   86 @ [stop dividing if remainder > 0]
           A    6 F [quotient from division]
           T    3 @ [update reduced n]
           E   75 @ [try another division]
    [86]   T      F [clear acc]
           A    6 @ [get residue for this prime]
    [88]   T      C [write back]
           A    9 @ [load negative prime count]
           A    2 F [inc count]
           E  103 @ [out if done all primes]
           T    9 @ [else update count]
           A   64 @ [inc addresses in the above code]
           A    2 F
           T   64 @
           A   66 @
           A    2 F
           T   66 @
           A   88 @
           A    2 F
           T   88 @
           E   63 @ [loop for next prime]

          [Tested all primes up to 31 for this n.
           Reduced n is now either 1 or a prime > 31]
   [103]   T      F
           A    3 @ [get reduced]
           S    2 F [subtract 2]
           G  111 @ [skip if reduced n = 1]
           A    2 F [else restore value]
           T    5 @ [copy to prime p]
   [109]   A  109 @ [for return from next]
           G   20 @ [call routine to update partial totient]
          [Update sum of Euler's totient over 1..n.
           Note sum is double word, while totient is single word.
           Totient is converted to double before adding to sum.]
   [111]   T      F [clear acc]
           T      D [clear 0D (i.e. 0F, 1F and sandwich bit)]
           A    4 @ [load totient (single word)]
           T      F [to 0F]
           A      D [load totient from 0D as double word]
           A     #@ [add to sum]
           T     #@ [update sum]

          [On to next n]
           A    8 @ [load negative count]
           A    2 F [add 1]
           G   49 @ [loop until count = 0]

          [Here when finished this step.
           Typically, n has increased by 100.
           Show n and the sum of Euler's totient.
           Note accumulator = 0 here.]
           T      D [clear 0D (i.e. 0F, 1F and sandwich bit)]
           A    2 @ [load n (single word)]
           T      F [to 0F; now 0D = n for printing]
   [124]   A  124 @ [for return from next]
           G   56 F [call library subroutine to print n]
           A     #@ [load sum (double word)]
           T      D [to 0D for printing]
   [128]   A  128 @ [for return from next]
           G   56 F [call library subroutine to print sum]
           O   14 @ [print new line (CR, LF)]
           O   15 @
          [On to next step]
           A    7 @ [load negative step count]
           A    2 F [add 1]
           G   47 @ [loop until count = 0]
          [Here when finished whole thing]
   [135]   O   16 @ [output null to flush teleprinter buffer]
           Z      F [stop]
           E   32 Z [define start of execution]
           P      F [start with accumulator = 0]

</lang>

Output:

     ORDER     TERMS
       100      3045
       200     12233
       300     27399
       400     48679
       500     76117
       600    109501
       700    149019
       800    194751
       900    246327
      1000    304193

Factor

Factor's ratio type automatically reduces fractions such as 0/1 and 1/1 to integers, so we print those separately at the beginning and ending of every sequence. This implementation makes use of the algorithm for calculating the next term from the wiki page [1]. It also makes use of Euler's totient function for recursively calculating the length [2]. <lang factor>USING: formatting io kernel math math.primes.factors math.ranges locals prettyprint sequences sequences.extras sets tools.time ; IN: rosetta-code.farey-sequence

! Given the order n and a farey pair, calculate the next member ! of the sequence.

p/q ( n a/b c/d -- p/q )

   a/b c/d [ >fraction ] bi@ :> ( a b c d )
   n b + d / >integer [ c * a - ] [ d * b - ] bi / ;

print-farey ( order -- )

   [ "F(%-2d): " printf ] [ 0 1 pick / ] bi "0/1 " write
   [ dup 1 = ] [ dup pprint bl 3dup p/q [ nip ] dip ] until
   3drop "1/1" print ;

φ ( n -- m ) ! Euler's totient function

   [ factors members [ 1 swap recip - ] map-product ] [ * ] bi ;

farey-length ( order -- length )

  dup 1 = [ drop 2 ]
  [ [ 1 - farey-length ] [ φ ] bi + ] if ;

part1 ( -- ) 11 [1,b] [ print-farey ] each nl ;

part2 ( -- )

   100 1,000 100 <range>
   [ dup farey-length "F(%-4d): %-6d members.\n" printf ] each ;

main ( -- ) [ part1 part2 nl ] time ;

MAIN: main</lang>

Output:

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
F(7 ): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
F(8 ): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
F(9 ): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

F(100 ): 3045   members.
F(200 ): 12233  members.
F(300 ): 27399  members.
F(400 ): 48679  members.
F(500 ): 76117  members.
F(600 ): 109501 members.
F(700 ): 149019 members.
F(800 ): 194751 members.
F(900 ): 246327 members.
F(1000): 304193 members.

Running time: 0.033974675 seconds

FreeBASIC

<lang freebasic>' version 05-04-2017 ' compile with: fbc -s console

' TRUE/FALSE are built-in constants since FreeBASIC 1.04 ' But we have to define them for older versions.

Ifndef TRUE

   #Define FALSE 0
   #Define TRUE Not FALSE

EndIf

Function farey(n As ULong, descending As Long) As ULong

   Dim As Long a, b = 1, c = 1, d = n, k
   Dim As Long aa, bb, cc, dd, count

   If descending = TRUE Then
       a = 1 : c = n -1
   End If

   count += 1
   If n < 12 Then Print Str(a); "/"; Str(b); " ";

   While ((c <= n) And Not descending) Or ((a > 0) And descending)
       aa = a : bb = b : cc = c : dd = d
       k = (n + b) \ d
       a = cc : b = dd : c = k * cc - aa : d = k * dd - bb
       count += 1
       If n < 12 Then Print Str(a); "/"; Str(b); " ";
   Wend

   If n < 12 Then Print

   Return count

End Function

' ------=< MAIN >=------

For i As Long = 1 To 11

   Print "F"; Str(i); " = ";
   farey(i, FALSE)

Next Print For i As Long= 100 To 1000 Step 100

   Print "F";Str(i);
   Print iif(i <> 1000, " ", ""); " = ";
   Print Using "######"; farey(i, FALSE)

Output:

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 
F7 = 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 
F8 = 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1 
F9 = 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 
F10 = 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1 
F11 = 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1 

F100  =   3045
F200  =  12233
F300  =  27399
F400  =  48679
F500  =  76117
F600  = 109501
F700  = 149019
F800  = 194751
F900  = 246327
F1000 = 304193

FunL

Translation of Python code at [3]. <lang funl>def farey( n ) =

 res = seq()
 a, b, c, d = 0, 1, 1, n
 res += "$a/$b"
 
 while c <= n
   k = (n + b)\d
   a, b, c, d = c, d, k*c - a, k*d - b
   res += "$a/$b"

for i <- 1..11

 println( "$i: ${farey(i).mkString(', ')}" )

for i <- 100..1000 by 100

 println( "$i: ${farey(i).length()}" )</lang>

Output:

1: 0/1, 1/1
2: 0/1, 1/2, 1/1
3: 0/1, 1/3, 1/2, 2/3, 1/1
4: 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1
5: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
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
7: 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1
8: 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1
9: 0/1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1/1
10: 0/1, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1/1
11: 0/1, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1/1
100: 3045
200: 12233
300: 27399
400: 48679
500: 76117
600: 109501
700: 149019
800: 194751
900: 246327
1000: 304193

Fōrmulæ

In this page you can see the solution of this task.

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.

The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.

Go

<lang go>package main

import "fmt"

type frac struct{ num, den int }

func (f frac) String() string {

   return fmt.Sprintf("%d/%d", f.num, f.den)

}

func f(l, r frac, n int) {

   m := frac{l.num + r.num, l.den + r.den}
   if m.den <= n {
       f(l, m, n)
       fmt.Print(m, " ")
       f(m, r, n)
   }

}

func main() {

   // task 1.  solution by recursive generation of mediants
   for n := 1; n <= 11; n++ {
       l := frac{0, 1}
       r := frac{1, 1}
       fmt.Printf("F(%d): %s ", n, l)
       f(l, r, n)
       fmt.Println(r)
   }
   // task 2.  direct solution by summing totient function
   // 2.1 generate primes to 1000
   var composite [1001]bool
   for _, p := range []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} {
       for n := p * 2; n <= 1000; n += p {
           composite[n] = true
       }
   }
   // 2.2 generate totients to 1000
   var tot [1001]int
   for i := range tot {
       tot[i] = 1
   }
   for n := 2; n <= 1000; n++ {
       if !composite[n] {
           tot[n] = n - 1
           for a := n * 2; a <= 1000; a += n {
               f := n - 1
               for r := a / n; r%n == 0; r /= n {
                   f *= n
               }
               tot[a] *= f
           }
       }
   }
   // 2.3 sum totients
   for n, sum := 1, 1; n <= 1000; n++ {
       sum += tot[n]
       if n%100 == 0 {
           fmt.Printf("|F(%d)|: %d\n", n, sum)
       }
   }

}</lang>

Output:

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
F(7): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
F(8): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
F(9): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
|F(100)|: 3045
|F(200)|: 12233
|F(300)|: 27399
|F(400)|: 48679
|F(500)|: 76117
|F(600)|: 109501
|F(700)|: 149019
|F(800)|: 194751
|F(900)|: 246327
|F(1000)|: 304193

Haskell

Generating an n'th order Farey sequence follows the algorithm described in Wikipedia. However, for fun, to generate a list of Farey sequences we generate only the highest order sequence, creating the rest by successively pruning the original. <lang Haskell>import Data.List (unfoldr, mapAccumR) import Data.Ratio ((%), denominator, numerator) import Text.Printf (PrintfArg, printf)

-- The n'th order Farey sequence. farey :: Integer -> [Rational] farey n = 0 : unfoldr step (0, 1, 1, n)

 where
   step (a, b, c, d)
     | c > n = Nothing
     | otherwise =
       let k = (n + b) `quot` d
       in Just (c %d, (c, d, k * c - a, k * d - b))

-- A list of pairs, (n, fn n), where fn is a function applied to the n'th order -- Farey sequence. We assume the list of orders is increasing. Only the -- highest order Farey sequence is evaluated; the remainder are generated by -- successively pruning this sequence. fareys :: ([Rational] -> a) -> [Integer] -> [(Integer, a)] fareys fn ns = snd $ mapAccumR prune (farey $ last ns) ns

 where
   prune rs n =
     let rs = filter ((<= n) . denominator) rs
     in (rs, (n, fn rs))

fprint

 :: (PrintfArg b)
 => String -> [(Integer, b)] -> IO ()

fprint fmt = mapM_ (uncurry $ printf fmt)

showFracs :: [Rational] -> String showFracs =

 unwords .
 map (concat . (<*>) [show . numerator, const "/", show . denominator] . pure)

main :: IO () main = do

 putStrLn "Farey Sequences\n"
 fprint "%2d %s\n" $ fareys showFracs [1 .. 11]
 putStrLn "\nSequence Lengths\n"
 fprint "%4d %d\n" $ fareys length [100,200 .. 1000]</lang>

Output:

Farey Sequences

 1 0/1 1/1
 2 0/1 1/2 1/1
 3 0/1 1/3 1/2 2/3 1/1
 4 0/1 1/4 1/3 1/2 2/3 3/4 1/1
 5 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
 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
 7 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
 8 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
 9 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

Sequence Lengths

 100 3045
 200 12233
 300 27399
 400 48679
 500 76117
 600 109501
 700 149019
 800 194751
 900 246327
1000 304193

J

Solution: <lang J>Farey=: x:@/:~@(0 , ~.)@(#~ <:&1)@:,@(%/~@(1 + i.)) NB. calculates Farey sequence displayFarey=: ('r/' charsub '0r' , ,&'r1')@": NB. displays Farey sequence according to task requirements order=: ': ' ,~ ": NB. display order of Farey sequence</lang>

Required examples:

<lang J> LF joinstring (order , displayFarey@Farey)&.> 1 + i.11 NB. Farey sequences, order 1-11 1: 0/0 1/1 2: 0/0 1/2 1/1 3: 0/0 1/3 1/2 2/3 1/1 4: 0/0 1/4 1/3 1/2 2/3 3/4 1/1 5: 0/0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 6: 0/0 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1 7: 0/0 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 8: 0/0 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1 9: 0/0 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 10: 0/0 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1 11: 0/0 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

  LF joinstring (order , ":@#@Farey)&.> 100 * 1 + i.10      NB. Count of Farey sequence items, order 100,200,..1000

100: 3045 200: 12233 300: 27399 400: 48679 500: 76117 600: 109501 700: 149019 800: 194751 900: 246327 1000: 304193</lang>

Java

Works with: Java version 1.5+

This example uses the fact that it generates the fraction candidates from the bottom up as well as Set's internal duplicate removal (based on Comparable.compareTo) to get rid of un-reduced fractions. It also uses TreeSet to sort based on the value of the fraction. <lang java5>import java.util.TreeSet;

public class Farey{ private static class Frac implements Comparable<Frac>{ int num; int den;

public Frac(int num, int den){ this.num = num; this.den = den; }

@Override public String toString(){ return num + "/" + den; }

@Override public int compareTo(Frac o){ return Double.compare((double)num / den, (double)o.num / o.den); } }

public static TreeSet<Frac> genFarey(int i){ TreeSet<Frac> farey = new TreeSet<Frac>(); for(int den = 1; den <= i; den++){ for(int num = 0; num <= den; num++){ farey.add(new Frac(num, den)); } } return farey; }

public static void main(String[] args){ for(int i = 1; i <= 11; i++){ System.out.println("F" + i + ": " + genFarey(i)); }

for(int i = 100; i <= 1000; i += 100){ System.out.println("F" + i + ": " + genFarey(i).size() + " members"); } } }</lang>

Output:

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]
F7: [0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1]
F8: [0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1]
F9: [0/1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1/1]
F10: [0/1, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1/1]
F11: [0/1, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1/1]
F100: 3045 members
F200: 12233 members
F300: 27399 members
F400: 48679 members
F500: 76117 members
F600: 109501 members
F700: 149019 members
F800: 194751 members
F900: 246327 members
F1000: 304193 members

Julia

Translation of: Java

<lang julia>using DataStructures

function farey(n::Int)

   rst = SortedSet{Rational}(Rational[0, 1])
   for den in 1:n, num in 1:den-1
       push!(rst, Rational(num, den))
   end
   return rst

end

for n in 1:11

   print("F_$n: ")
   for frac in farey(n)
       print(numerator(frac), "/", denominator(frac), " ")
   end
   println()

end

for n in 100:100:1000

   println("F_$n has ", length(farey(n)), " fractions")

end</lang>

Output:

F_1: 0/1 1/1 
F_2: 0/1 1/2 1/1 
F_3: 0/1 1/2 1/3 2/3 1/1 
F_4: 0/1 1/2 1/3 2/3 1/4 3/4 1/1 
F_5: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/1 
F_6: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/1 
F_7: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/1 
F_8: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/8 3/8 5/8 7/8 1/1 
F_9: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/8 3/8 5/8 7/8 1/9 2/9 4/9 5/9 7/9 8/9 1/1 
F_10: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/8 3/8 5/8 7/8 1/9 2/9 4/9 5/9 7/9 8/9 1/10 3/10 7/10 9/10 1/1 
F_11: 0/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/8 3/8 5/8 7/8 1/9 2/9 4/9 5/9 7/9 8/9 1/10 3/10 7/10 9/10 1/11 2/11 3/11 4/11 5/11 6/11 7/11 8/11 9/11 10/11 1/1 
F_100 has 3045 fractions
F_200 has 12233 fractions
F_300 has 27399 fractions
F_400 has 48679 fractions
F_500 has 76117 fractions
F_600 has 109501 fractions
F_700 has 149019 fractions
F_800 has 194751 fractions
F_900 has 246327 fractions
F_1000 has 304193 fractions

Kotlin

<lang scala>// version 1.1

fun farey(n: Int): List<String> {

   var a = 0
   var b = 1
   var c = 1
   var d = n
   val f = mutableListOf("$a/$b")
   while (c <= n) {
       val k = (n + b) / d
       val aa = a
       val bb = b
       a = c
       b = d
       c = k * c - aa
       d = k * d - bb
       f.add("$a/$b")
   }
   return f.toList()

}

fun main(args: Array<String>) {

   for (i in 1..11)
       println("${"%2d".format(i)}: ${farey(i).joinToString(" ")}")
   println()
   for (i in 100..1000 step 100)
       println("${"%4d".format(i)}: ${"%6d".format(farey(i).size)} fractions")

}</lang>

Output:

 1: 0/1 1/1
 2: 0/1 1/2 1/1
 3: 0/1 1/3 1/2 2/3 1/1
 4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
 5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
 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
 7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
 8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
 9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

 100:   3045 fractions
 200:  12233 fractions
 300:  27399 fractions
 400:  48679 fractions
 500:  76117 fractions
 600: 109501 fractions
 700: 149019 fractions
 800: 194751 fractions
 900: 246327 fractions
1000: 304193 fractions

langur

Prior to 0.10, multi-variable declarations/assignments would use parentheses on the variable names and values.

Works with: langur version 0.10

<lang langur>val .farey = f(.n) {

   var .a, .b, .c, .d = 0, 1, 1, .n
   while[=0, 1] .c <= .n {
       val .k = (.n + .b) // .d
       .a, .b, .c, .d = .c, .d, .k x .c - .a, .k x .d - .b
       _while ~= .a, .b
   }

}

writeln "Farey sequence for orders 1 through 11" for .i of 11 {

   writeln $"\.i:2;: ", join " ", map(f $"\.f[1];/\.f[2];", .farey(.i))

}</lang>

Theoretically, the following should work, but it's way too SLOW to run in langur 0.10. Maybe another release will be fast enough. <lang langur>writeln "count of Farey sequence fractions for 100 to 1000 by hundreds" for .i = 100; .i <= 1000; .i += 100 {

   writeln $"\.i:4;: ", len(.farey(.i))

}</lang>

Lua

<lang Lua>-- Return farey sequence of order n function farey (n)

   local a, b, c, d, k = 0, 1, 1, n
   local farTab = Template:A, b
   while c <= n do
       k = math.floor((n + b) / d)
       a, b, c, d = c, d, k * c - a, k * d - b
       table.insert(farTab, {a, b})
   end
   return farTab

end

-- Main procedure for i = 1, 11 do

   io.write(i .. ": ")
   for _, frac in pairs(farey(i)) do io.write(frac[1] .. "/" .. frac[2] .. " ") end
   print()

end for i = 100, 1000, 100 do print(i .. ": " .. #farey(i) .. " items") end</lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045 items
200: 12233 items
300: 27399 items
400: 48679 items
500: 76117 items
600: 109501 items
700: 149019 items
800: 194751 items
900: 246327 items
1000: 304193 items

Maple

<lang Maple>#Displays terms in Farey_sequence of order n farey_sequence := proc(n) local a,b,c,d,k; a,b,c,d := 0,1,1,n; printf("%d/%d", a,b); while(c <= n) do k := trunc((n+b)/d); a,b,c,d := c,d,c*k-a,d*k-b; printf(", %d/%d", a,b); end do; printf("\n"); end proc;

Returns the length of a Farey sequence

farey_len := proc(n) return 1 + add(NumberTheory:-Totient(k), k=1..n); end proc;

for i to 11 do farey_sequence(i); end do; printf("\n"); for j from 100 to 1000 by 100 do printf("%d\n", farey_len(j)); end do;</lang>

F('), write(I100), write('):

.uniq.sort

end

end

puts 'Farey sequence for order 1 through 11 (inclusive):' for n in 1..11

 puts "F(#{n}): " + farey(n).join(", ")

end puts 'Number of fractions in the Farey sequence:' for i in (100..1000).step(100)

 puts "F(%4d) =%7d" % [i, farey(i, true)]

end</lang>

Output:

Farey sequence for order 1 through 11 (inclusive):
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
F(7): 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1
F(8): 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1
F(9): 0/1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1/1
F(10): 0/1, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1/1
F(11): 0/1, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1/1
Number of fractions in the Farey sequence:
F( 100) =   3045
F( 200) =  12233
F( 300) =  27399
F( 400) =  48679
F( 500) =  76117
F( 600) = 109501
F( 700) = 149019
F( 800) = 194751
F( 900) = 246327
F(1000) = 304193

Rust

<lang rust>#[derive(Copy, Clone)] struct Fraction {

   numerator: u32,
   denominator: u32,

}

use std::fmt;

impl fmt::Display for Fraction {

   fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
       write!(f, "{}/{}", self.numerator, self.denominator)
   }

}

impl Fraction {

   fn new(n: u32, d: u32) -> Fraction {
       Fraction {
           numerator: n,
           denominator: d,
       }
   }

}

fn farey_sequence(n: u32) -> impl std::iter::Iterator<Item = Fraction> {

   let mut a = 0;
   let mut b = 1;
   let mut c = 1;
   let mut d = n;
   std::iter::from_fn(move || {
       if a > n {
           return None;
       }
       let result = Fraction::new(a, b);
       let k = (n + b) / d;
       let next_c = k * c - a;
       let next_d = k * d - b;
       a = c;
       b = d;
       c = next_c;
       d = next_d;
       Some(result)
   })

}

fn main() {

   for n in 1..=11 {
       print!("{}:", n);
       for f in farey_sequence(n) {
           print!(" {}", f);
       }
       println!();
   }
   for n in (100..=1000).step_by(100) {
       println!("{}: {}", n, farey_sequence(n).count());
   }

}</lang>

Output:

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045
200: 12233
300: 27399
400: 48679
500: 76117
600: 109501
700: 149019
800: 194751
900: 246327
1000: 304193

Scala

<lang scala> object FareySequence {

 def fareySequence(n: Int, start: (Int, Int), stop: (Int, Int)): LazyList[(Int, Int)] = {
   val (nominator_l, denominator_l) = start
   val (nominator_r, denominator_r) = stop

   val mediant = ((nominator_l + nominator_r), (denominator_l + denominator_r))

   if (mediant._2 <= n) fareySequence(n, start, mediant) ++ mediant #:: fareySequence(n, mediant, stop)
   else LazyList.empty
 }

 def farey(n: Int, start: (Int, Int) = (0, 1), stop: (Int, Int) = (1, 1)): LazyList[(Int, Int)] = {
   start #:: fareySequence(n, start, stop) ++ stop #:: LazyList.empty[(Int, Int)]
 }

 def main(args: Array[String]): Unit = {
   for (i <- 1 to 11) {
     println(s"$i: " + farey(i).map(e => s"${e._1}/${e._2}").mkString(", "))
   }
   println
   for (i <- 100 to 1000 by 100) {
     println(s"$i: " + farey(i).length + " elements")
   }
 }

} </lang>

Output:

1: 0/1, 1/1
2: 0/1, 1/2, 1/1
3: 0/1, 1/3, 1/2, 2/3, 1/1
4: 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1
5: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
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
7: 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1
8: 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1
9: 0/1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1/1
10: 0/1, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1/1
11: 0/1, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1/1

100: 3045 elements
200: 12233 elements
300: 27399 elements
400: 48679 elements
500: 76117 elements
600: 109501 elements
700: 149019 elements
800: 194751 elements
900: 246327 elements
1000: 304193 elements

Scheme

<lang scheme> (import (scheme base)

       (scheme write))

create a generator for Farey sequence n using next term formula from https://en.wikipedia.org/wiki/Farey_sequence

(define (farey-generator n)

 (let ((a #f) (b 1) (c #f) (d n))
   (lambda ()
     (cond ((not a)    ; first item in sequence
            (set! a 0)
            (/ a b))
           ((not c)    ; second item in sequence
            (set! c 1)
            (/ c d))
           ((= c d)    ; return #f when finished sequence
            #f) 
           (else       ; compute next term 
             (let* ((f (floor (/ (+ n b) d)))
                    (p (- (* f c) a))
                    (q (- (* f d) b)))
               (set! a c)
               (set! b d)
               (set! c p)
               (set! d q)
               (/ p q)))))))

(define (farey-sequence n display?)

 (define (display-rat n) ; ensure 0,1 show /1
   (display n)
   (when (= 1 (denominator n))
     (display "/1"))
   (display " "))
 ;
 (let ((gen (farey-generator n)))
   (do ((res (gen) (gen))
        (count 0 (+ 1 count)))
     ((not res) (when display? (newline)) 
                count)
     (when display? (display-rat res)))))

(display "Farey sequence for order 1 through 11 (inclusive):\n") (do ((i 1 (+ i 1)))

 ((> i 11) )
 (display (string-append "F(" (number->string i) "): "))
 (farey-sequence i #t))

(display "\nNumber of fractions in the Farey sequence:\n") (do ((i 100 (+ i 100)))

 ((> i 1000) )
 (display 
   (string-append "F(" (number->string i) ") = "
                  (number->string (farey-sequence i #f))))
 (newline))

</lang>

Output:

Farey sequence for order 1 through 11 (inclusive):
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 
F(7): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 
F(8): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1 
F(9): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1 
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1 

Number of fractions in the Farey sequence:
F(100) = 3045
F(200) = 12233
F(300) = 27399
F(400) = 48679
F(500) = 76117
F(600) = 109501
F(700) = 149019
F(800) = 194751
F(900) = 246327
F(1000) = 304193

Sidef

<lang ruby>func farey_count(n) { # A005728

   1 + sum(1..n, {|k| euler_phi(k) })

}

func farey(n) {

   var seq = [0]
   var (a,b,c,d) = (0,1,1,n)

   while (c <= n) {
       var k = (n+b)//d
       (a,b,c,d) = (c, d, k*c - a, k*d - b)
       seq << a/b
   }

   return seq

}

say "Farey sequence for order 1 through 11 (inclusive):" for n in (1..11) {

   say("F(%2d): %s" % (n, farey(n).map{.as_frac}.join(" ")))

}

say "\nNumber of fractions in the Farey sequence:" for n in (100..1000 -> by(100)) {

   say ("F(%4d) =%7d" % (n, farey_count(n)))

}</lang>

Output:

Farey sequence for order 1 through 11 (inclusive):
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
F( 7): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
F( 8): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
F( 9): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

Number of fractions in the Farey sequence:
F( 100) =   3045
F( 200) =  12233
F( 300) =  27399
F( 400) =  48679
F( 500) =  76117
F( 600) = 109501
F( 700) = 149019
F( 800) = 194751
F( 900) = 246327
F(1000) = 304193

Stata

<lang stata>mata function totient(n_) { n = n_ if (n<4) { if (n<1) return(.) else if (n>1) return(n-1) else return(1) } else { r = 1 if (mod(n,2)==0) { n = floor(n/2) while (mod(n,2)==0) { n = floor(n/2) r = r*2 } } for (k=3; k*k<=n; k=k+2) { if (mod(n,k)==0) { r = r*(k-1) n = floor(n/k) while (mod(n,k)==0) { n = floor(n/k) r = r*k } } } if (n>1) r = r*(n-1) return(r) } }

function map(f,a) { n = rows(a) p = cols(a) b = J(n,p,.) for (i=1; i<=n; i++) { for (j=1; j<=p; j++) { b[i,j] = (*f)(a[i,j]) } } return(b) }

function farey_length(n) { return(1+sum(map(&totient(),1::n))) }

function farey(n) { m = 1+sum(map(&totient(),1::n)) r = J(m,2,.) r[1,.] = 0,1 a = 0 b = 1 c = 1 d = n i = 1 while (c<=n) { k = floor((n+b)/d) a = k*c-a b = k*d-b swap(a,c) swap(b,d) r[++i,.] = a,b } return(r) }

for (n=1; n<=11; n++) { a = farey(n) m = rows(a) for (i=1; i<=m; i++) printf("%f/%f ",a[i,1],a[i,2]) printf("\n") }

map(&farey_length(),100*(1..10)) end</lang>

Output

0/1 1/1 
0/1 1/2 1/1 
0/1 1/3 1/2 2/3 1/1 
0/1 1/4 1/3 1/2 2/3 3/4 1/1 
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 
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 
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 
0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1 
0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 
0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1 
0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

            1        2        3        4        5        6        7        8        9       10
    +-------------------------------------------------------------------------------------------+
  1 |    3045    12233    27399    48679    76117   109501   149019   194751   246327   304193  |
    +-------------------------------------------------------------------------------------------+

Swift

Class with computed properties: <lang swift>class Farey {

   let n: Int

   init(_ x: Int) {
       n = x
   }

   //using algorithm from wikipedia
   var sequence: [(Int,Int)] {
       var a = 0
       var b = 1
       var c = 1
       var d = n
       var results = [(a, b)]
       while c <= n {
           let k = (n + b) / d
           let oldA = a
           let oldB = b
           a = c
           b = d
           c = k * c - oldA
           d = k * d - oldB
           results += [(a, b)]
       }
       return results
   }

   var formattedSequence: String {
       var s = "\(n):"
       for pair in sequence {
           s += " \(pair.0)/\(pair.1)"
       }
       return s
   }

}

print("Sequences\n")

for n in 1...11 {

   print(Farey(n).formattedSequence)

}

print("\nSequence Lengths\n")

for n in 1...10 {

   let m = n * 100
   print("\(m): \(Farey(m).sequence.count)")

}</lang>

Output:

Sequences

1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
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
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

Sequence Lengths

100: 3045
200: 12233
300: 27399
400: 48679
500: 76117
600: 109501
700: 149019
800: 194751
900: 246327
1000: 304193

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

proc farey {n} {

   set nums [lrepeat [expr {$n+1}] 1]
   set result Template:0 1
   for {set found 1} {$found} {} {

set nj [lindex $nums [set j 1]] for {set found 0;set i 1} {$i <= $n} {incr i} { if {[lindex $nums $i]*$j < $nj*$i} { set nj [lindex $nums [set j $i]] set found 1 } } lappend result [list $nj $j] for {set i $j} {$i <= $n} {incr i $j} { lset nums $i [expr {[lindex $nums $i] + 1}] }

   }
   return $result

}

for {set i 1} {$i <= 11} {incr i} {

   puts F($i):\x20[lmap n [farey $i] {join $n /}]

} for {set i 100} {$i <= 1000} {incr i 100} {

   puts |F($i)|\x20=\x20[llength [farey $i]]

}</lang>

Output:

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
F(7): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
F(8): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
F(9): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
|F(100)| = 3045
|F(200)| = 12233
|F(300)| = 27399
|F(400)| = 48679
|F(500)| = 76117
|F(600)| = 109501
|F(700)| = 149019
|F(800)| = 194751
|F(900)| = 246327
|F(1000)| = 304193

Vala

Translation of: Nim

<lang vala>struct Fraction {

 public uint d;
 public uint n;

}

void farey(uint n) {

 Fraction f1 = {0, 1};
 Fraction f2 = {1, n};
 print("0/1 1/%u ", n);
 while (f2.n > 1) {
   var k = (n + f1.n) / f2.n;
   var aux = f1;
   f1 = f2;
   f2 = {f2.d * k - aux.d, f2.n * k - aux.n};
   print("%u/%u ", f2.d, f2.n);
 }
 print("\n");

}

uint fareyLength(uint n, uint[] cache) {

 if (n >= cache.length) {
   uint newLen = cache.length;
   if (newLen == 0) 
     newLen = 16;
   while (newLen <= n) 
     newLen *= 2;
   cache.resize((int)newLen);
 }
 else if (cache[n] != 0)
   return cache[n];
 
 uint length = n * (n + 3) / 2;
 for (uint p = 2, q = 2; p <= n; p = q) {
   q = n / (n / p) + 1;
   length -= fareyLength(n / p, cache) * (q - p);
 }

 cache[n] = length;
 return length;

}

void main() {

 for (uint n = 1; n < 12; n++)
 {
   print("%8u: ", n);
   farey(n);
 }
 
 uint[] cache = new uint[0];
 for (uint n = 100; n <= 1000; n += 100)
   print("%8u: %14u items\n", n, fareyLength(n, cache));

}</lang>

Output:

       1: 0/1 1/1 
       2: 0/1 1/2 1/1 
       3: 0/1 1/3 1/2 2/3 1/1 
       4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1 
       5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 
       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 
       7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 
       8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1 
       9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 
      10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1 
      11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1 
     100:           3045 items
     200:          12233 items
     300:          27399 items
     400:          48679 items
     500:          76117 items
     600:         109501 items
     700:         149019 items
     800:         194751 items
     900:         246327 items
    1000:         304193 items

Wren

Translation of: Go

Library: Wren-math

Library: Wren-trait

Library: Wren-fmt

Library: Wren-rat

<lang ecmascript>import "/math" for Int import "/trait" for Stepped import "/fmt" for Fmt import "/rat" for Rat

var f //recursive f = Fn.new { |l, r, n|

   var m = Rat.new(l.num + r.num, l.den + r.den)
   if (m.den <= n) {
       f.call(l, m, n)
       System.write("%(m) ")
       f.call(m, r, n)
   }

}

/* Task 1: solution by recursive generation of mediants. */ for (n in 1..11) {

   var l = Rat.zero
   var r = Rat.one
   System.write("F(%(n)): %(l) ")
   f.call(l, r, n)
   System.print(r)

} System.print()

/* Task 2: direct solution by summing totient function. */

// generate primes to 1000 var comp = Int.primeSieve(1001, false)

// generate totients to 1000 var tot = List.filled(1001, 1) for (n in 2..1000) {

   if (!comp[n]) {
       tot[n] = n - 1
       for (a in Stepped.ascend(n*2..1000, n)) {
           var f = n - 1
           var r = (a/n).floor
           while (r%n == 0) {
               f = f * n
               r = (r/n).floor
           }
           tot[a] = tot[a] * f
       }
   }

}

// sum totients var sum = 1 for (n in 1..1000) {

   sum = sum + tot[n]
   if (n%100 == 0) System.print("F(%(Fmt.d(4, n))): %(Fmt.dc(7, sum))")

}</lang>

Output:

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
F(7): 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
F(8): 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
F(9): 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
F(10): 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

F( 100):   3,045
F( 200):  12,233
F( 300):  27,399
F( 400):  48,679
F( 500):  76,117
F( 600): 109,501
F( 700): 149,019
F( 800): 194,751
F( 900): 246,327
F(1000): 304,193

zkl

Translation of: C

<lang zkl>fcn farey(n){

  f1,f2:=T(0,1),T(1,n);  // fraction is (num,dnom)
  print("%d/%d %d/%d".fmt(0,1,1,n));
  while(f2[1]>1){
     k,t  :=(n + f1[1])/f2[1], f1;
     f1,f2 = f2,T(f2[0]*k - t[0], f2[1]*k - t[1]);
     print(" %d/%d".fmt(f2.xplode()));
  }
  println();

}</lang> <lang zkl>foreach n in ([1..11]){ print("%2d: ".fmt(n)); farey(n); }</lang>

Output:

 1: 0/1 1/1
 2: 0/1 1/2 1/1
 3: 0/1 1/3 1/2 2/3 1/1
 4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
 5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
 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
 7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
 8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
 9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

<lang zkl>fcn farey_len(n){

  var cache=Dictionary();	// 107 keys to 1,000; 6323@10,000,000
  if(z:=cache.find(n)) return(z);

  len,p,q := n*(n + 3)/2, 2,0;
  while(p<=n){
     q=n/(n/p) + 1;
     len-=self.fcn(n/p) * (q - p);
     p=q;
  }
  cache[n]=len;   // len is returned

}</lang> <lang zkl>foreach n in ([100..1000,100]){

  println("%4d: %7,d items".fmt(n,farey_len(n)));

} n:=0d10_000_000; println("\n%,d: %,d items".fmt(n,farey_len(n)));</lang>

Output:

 100:   3,045 items
 200:  12,233 items
 300:  27,399 items
 400:  48,679 items
 500:  76,117 items
 600: 109,501 items
 700: 149,019 items
 800: 194,751 items
 900: 246,327 items
1000: 304,193 items

10,000,000: 30,396,356,427,243 items