Farey sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
No edit summary
Line 1,077: Line 1,077:
900: 246327 items
900: 246327 items
1000: 304193 items</pre>
1000: 304193 items</pre>

=={{header|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>
{{Out|Output}
<pre>
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

3045
12233
27399
48679
76117
109501
149019
194751
246327
304193
</pre>


=={{header|Mathematica}}==
=={{header|Mathematica}}==

Revision as of 13:57, 4 May 2018

Task
Farey sequence
You are encouraged to solve this task according to the task description, using any language you may know.

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:





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


See also



AWK

<lang AWK>

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

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

C

<lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. 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

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


(loop for i from 1 to 11 do 

    (format t "~a: ~{~a ~}~%" 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 
2: 0 1/2 1 
3: 0 1/3 1/2 2/3 1 
4: 0 1/4 1/3 1/2 2/3 3/4 1 
5: 0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1 
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 
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 
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 
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 
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 
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 

NIL

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.

NIL

D

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

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

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.

  1. Ifndef TRUE
   #Define FALSE 0
   #Define TRUE Not FALSE
  1. 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)

Next

' empty keyboard buffer While Inkey <> "" : Wend Print : Print "hit any key to end program" Sleep End</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
F200  =  12233
F300  =  27399
F400  =  48679
F500  =  76117
F600  = 109501
F700  = 149019
F800  = 194751
F900  = 246327
F1000 = 304193

FunL

Translation of Python code at [1]. <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

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

J has an internal data representation for completely reduced rational numbers. This displays as integers where that is possible and otherwise displays as NNNrDDD where the part to the left of the 'r' is the numerator and the part to the right of the 'r' is the denominator.

This mechanism is a part of J's "constant language", and is similar to scientific notation (which uses an 'e' instead of an 'r') and with J's complex number notation (which uses a 'j' instead of an 'r'), and which follow similar display rules.

This mechanism also hints that J's type promotion rules are designed to give internally consistent results a priority. As much as possible you do not get different results from the same operation just because you "used a different data type". J's design adopts the philosophy that "different results from the same operation based on different types" is likely to introduce errors in thinking. (Of course there are machine limits and certain floating point operations tend to introduce internal inconsistencies, but those are mentioned only in passing - they are not directly relevant to this task.)

<lang J>Farey=:3 :0 

 0,/:~~.(#~ <:&1),%/~1x+i.y

)</lang>

Required examples:

<lang J> Farey 1 0 1 

  Farey 2

0 1r2 1 

  Farey 3

0 1r3 1r2 2r3 1 

  Farey 4

0 1r4 1r3 1r2 2r3 3r4 1 

  Farey 5

0 1r5 1r4 1r3 2r5 1r2 3r5 2r3 3r4 4r5 1 

  Farey 6

0 1r6 1r5 1r4 1r3 2r5 1r2 3r5 2r3 3r4 4r5 5r6 1 

  Farey 7

0 1r7 1r6 1r5 1r4 2r7 1r3 2r5 3r7 1r2 4r7 3r5 2r3 5r7 3r4 4r5 5r6 6r7 1 

  Farey 8

0 1r8 1r7 1r6 1r5 1r4 2r7 1r3 3r8 2r5 3r7 1r2 4r7 3r5 5r8 2r3 5r7 3r4 4r5 5r6 6r7 7r8 1 

  Farey 9

0 1r9 1r8 1r7 1r6 1r5 2r9 1r4 2r7 1r3 3r8 2r5 3r7 4r9 1r2 5r9 4r7 3r5 5r8 2r3 5r7 3r4 7r9 4r5 5r6 6r7 7r8 8r9 1 

  Farey 10

0 1r10 1r9 1r8 1r7 1r6 1r5 2r9 1r4 2r7 3r10 1r3 3r8 2r5 3r7 4r9 1r2 5r9 4r7 3r5 5r8 2r3 7r10 5r7 3r4 7r9 4r5 5r6 6r7 7r8 8r9 9r10 1 

  Farey 11

0 1r11 1r10 1r9 1r8 1r7 1r6 2r11 1r5 2r9 1r4 3r11 2r7 3r10 1r3 4r11 3r8 2r5 3r7 4r9 5r11 1r2 6r11 5r9 4r7 3r5 5r8 7r11 2r3 7r10 5r7 8r11 3r4 7r9 4r5 9r11 5r6 6r7 7r8 8r9 9r10 10r11 1 

  (,. #@Farey"0) 100*1+i.10
100   3045
200  12233
300  27399
400  48679
500  76117
600 109501
700 149019
800 194751
900 246327

1000 304193</lang>

Optimized

A small change in the 'Farey' function makes the last request, faster.

A second change in the 'Farey' function makes the last request, much faster.

A third change in the 'Farey' function makes the last request, again, a little bit faster.

Even if it is 20 times faster, the response time is just acceptable. Now the response time is quite satisfactory.

The script produces the sequences in rational number notation as well in fractional number notation.

<lang J>Farey=: 3 : '/:~,&0 1~.(#~<&1),(1&+%/2&+)i.y-1'

NB. rational number notation rplc&(' 0';'= 0r0');,&('r1',LF)@:,~&'F'@:":@:x:&.>(,Farey)&.>1+i.11

NB. fractional number notation rplc&('r';'/';' 0';'= 0/0');,&('r1',LF)@:,~&'F'@:":@:x:&.>(,Farey)&.>1+i.11

NB. number of fractions

,&(' items',LF)@
,~&'F'@:":&.>(,.#@:Farey)&.>100*1+i.10</lang>
Output:
F1= 0r0 1r1
F2= 0r0 1r2 1r1
F3= 0r0 1r3 1r2 2r3 1r1
F4= 0r0 1r4 1r3 1r2 2r3 3r4 1r1
F5= 0r0 1r5 1r4 1r3 2r5 1r2 3r5 2r3 3r4 4r5 1r1
F6= 0r0 1r6 1r5 1r4 1r3 2r5 1r2 3r5 2r3 3r4 4r5 5r6 1r1
F7= 0r0 1r7 1r6 1r5 1r4 2r7 1r3 2r5 3r7 1r2 4r7 3r5 2r3 5r7 3r4 4r5 5r6 6r7 1r1
F8= 0r0 1r8 1r7 1r6 1r5 1r4 2r7 1r3 3r8 2r5 3r7 1r2 4r7 3r5 5r8 2r3 5r7 3r4 4r5 5r6 6r7 7r8 1r1
F9= 0r0 1r9 1r8 1r7 1r6 1r5 2r9 1r4 2r7 1r3 3r8 2r5 3r7 4r9 1r2 5r9 4r7 3r5 5r8 2r3 5r7 3r4 7r9 4r5 5r6 6r7 7r8 8r9 1r1
F10= 0r0 1r10 1r9 1r8 1r7 1r6 1r5 2r9 1r4 2r7 3r10 1r3 3r8 2r5 3r7 4r9 1r2 5r9 4r7 3r5 5r8 2r3 7r10 5r7 3r4 7r9 4r5 5r6 6r7 7r8 8r9 9r10 1r1
F11= 0r0 1r11 1r10 1r9 1r8 1r7 1r6 2r11 1r5 2r9 1r4 3r11 2r7 3r10 1r3 4r11 3r8 2r5 3r7 4r9 5r11 1r2 6r11 5r9 4r7 3r5 5r8 7r11 2r3 7r10 5r7 8r11 3r4 7r9 4r5 9r11 5r6 6r7 7r8 8r9 9r10 10r11 1r1

F1= 0/0 1/1
F2= 0/0 1/2 1/1
F3= 0/0 1/3 1/2 2/3 1/1
F4= 0/0 1/4 1/3 1/2 2/3 3/4 1/1
F5= 0/0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
F6= 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
F7= 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
F8= 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
F9= 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
F10= 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
F11= 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

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

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)::OrderedSet{Rational} 

   rst = OrderedSet{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

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;

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


Scala

<lang scala> object Farey { 

 def fareySequence(n: Int, start: (Int, Int), stop: (Int, Int)): Stream[(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 Stream.empty
 }

 def farey(n: Int, start: (Int, Int) = (0, 1), stop: (Int, Int) = (1, 1)): Stream[(Int, Int)] = {
   start #:: fareySequence(n, start, stop) ++ stop #:: Stream.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

Translation of: Ruby

<lang ruby>func farey_count(n) { 

   (n*(n+3))//2 - (2..n -> sum_by {|k| farey_count(n//k) })

}

func farey(n) { 

   gather {
       1..n -> each {|k| 0..k -> each {|m| take(m/k) }}
   }.uniq.sort

}

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 'Number of fractions in the Farey sequence:' for i in (100..1000 -> by(100)) { 

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

}</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

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
Retrieved from "https://rosettacode.org/wiki/Farey_sequence?oldid=245302"