Farey sequence: Difference between revisions
(→{{header|C}}: separate print and count functions; add caching) |
|||
Line 25: | Line 25: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
|||
#include <string.h> |
|||
void farey(int n) |
|||
{ |
{ |
||
typedef struct { int d, n; } frac; |
typedef struct { int d, n; } frac; |
||
frac f1 = {0, 1}, f2 = {1, n}, t; |
frac f1 = {0, 1}, f2 = {1, n}, t; |
||
int k |
int k; |
||
printf("%d/%d %d/%d", 0, 1, 1, n); |
|||
while (f2.n > 1) { |
|||
k = (n + f1.n) / f2.n; |
k = (n + f1.n) / f2.n; |
||
t = f1, f1 = f2, f2 = (frac) { f2.d * k - t.d, f2.n * k - t.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 k; |
|||
for (k = 2; k <= n; k++) |
|||
len -= farey_len(n/k); |
|||
cache[n] = len; |
|||
return len; |
return len; |
||
} |
} |
||
Line 48: | Line 74: | ||
for (n = 1; n <= 11; n++) { |
for (n = 1; n <= 11; n++) { |
||
printf("%d: ", n); |
printf("%d: ", n); |
||
farey(n |
farey(n); |
||
} |
} |
||
for (n = 100; n <= 1000; n += 100) |
for (n = 100; n <= 1000; n += 100) |
||
printf("%d: % |
printf("%d: %llu items\n", n, farey_len(n)); |
||
n = 10000000; |
|||
printf("\n%d: %llu items\n", n, farey_len(n)); |
|||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
Line 79: | Line 107: | ||
900: 246327 items |
900: 246327 items |
||
1000: 304193 items |
1000: 304193 items |
||
10000000: 30396356427243 items |
|||
</pre> |
</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
This imports the module from the Arithmetic/Rational task. |
This imports the module from the Arithmetic/Rational task. |
Revision as of 20:47, 1 April 2014
The Farey sequence (sometimes incorrectly called a Farey series) of order is the sequence of completely reduced fractions between and which, when in lowest terms, have denominators less than or equal to , arranged in order of increasing size.
Each Farey sequence starts with value , denoted by the fraction and ends with the value , denoted by the fraction . The Farey sequences of orders to are:
- Task
- Compute and show the Farey sequence for orders through (inclusive).
- Compute and display the number of fractions in the Farey sequence for order through (inclusive) by hundreds.
- See also
- Sequence A006842 numerators of Farey series of order 1, 2, ··· on OEIS.
- Sequence A006843 denominators of Farey series of order 1, 2, ··· on OEIS.
- Sequence A005728 number of fractions in Farey series of order n. on OEIS.
- Entry Farey sequence on Mathworld.
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 k; for (k = 2; k <= n; k++) len -= farey_len(n/k);
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
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*/ {
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() {
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]
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
Perl 6
<lang perl6>sub farey ($order) { uniq 0/1, (1..$order).map: { (1..$^d).map: { $^n/$d } } }
say "Farey sequence order "; say "$_: ", .&farey.sort.map: *.nude.join('/') for 1..11; say "Farey sequence order $_ has ", [.&farey].elems, ' elements.' for 100, 200 ... 1000;</lang>
- Output:
Farey sequence order 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 order 100 has 3045 elements. Farey sequence order 200 has 12233 elements. Farey sequence order 300 has 27399 elements. Farey sequence order 400 has 48679 elements. Farey sequence order 500 has 76117 elements. Farey sequence order 600 has 109501 elements. Farey sequence order 700 has 149019 elements. Farey sequence order 800 has 194751 elements. Farey sequence order 900 has 246327 elements. Farey sequence order 1000 has 304193 elements.
Python
<lang python>from fractions import Fraction
class Fr(Fraction):
def __repr__(self): return '(%s/%s)' % (self.numerator, self.denominator)
def farey(n, length=False):
if not length: return [Fr(0, 1)] + sorted({Fr(m, k) for k in range(1, n+1) for m in range(1, k+1)}) else: #return 1 + len({Fr(m, k) for k in range(1, n+1) for m in range(1, k+1)}) return (n*(n+3))//2 - sum(farey(n//k, True) for k in range(2, n+1))
if __name__ == '__main__':
print('Farey sequence for order 1 through 11 (inclusive):') for n in range(1, 12): print(farey(n)) print('Number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds:') print([farey(i, length=True) for i in range(100, 1001, 100)])</lang>
- Output:
Farey sequence for order 1 through 11 (inclusive): [(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)] Number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds: [3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193]
Racket
Once again, racket's math/number-theory package comes to the rescue! <lang racket>#lang racket (require math/number-theory) (define (display-farey-sequence order show-fractions?)
(define f-s (farey-sequence order)) (printf "-- Farey Sequence for order ~a has ~a fractions~%" order (length f-s)) ;; racket will simplify 0/1 and 1/1 to 0 and 1 respectively, so deconstruct into numerator and ;; denomimator (and take the opportunity to insert commas (when show-fractions? (displayln (string-join (for/list ((f f-s)) (format "~a/~a" (numerator f) (denominator f))) ", "))))
- compute and show the Farey sequence for order
- 1 through 11 (inclusive).
(for ((order (in-range 1 (add1 11)))) (display-farey-sequence order #t))
- compute and display the number of fractions in the Farey sequence for order
- 100 through 1,000 (inclusive) by hundreds.
(for ((order (in-range 100 (add1 1000) 100))) (display-farey-sequence order #f))</lang>
- Output:
-- Farey Sequence for order 1 has 2 fractions 0/1, 1/1 -- Farey Sequence for order 2 has 3 fractions 0/1, 1/2, 1/1 -- Farey Sequence for order 3 has 5 fractions 0/1, 1/3, 1/2, 2/3, 1/1 -- Farey Sequence for order 4 has 7 fractions 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1 -- Farey Sequence for order 5 has 11 fractions 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1 -- Farey Sequence for order 6 has 13 fractions 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 -- Farey Sequence for order 7 has 19 fractions 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 -- Farey Sequence for order 8 has 23 fractions 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 -- Farey Sequence for order 9 has 29 fractions 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 -- Farey Sequence for order 10 has 33 fractions 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 -- Farey Sequence for order 11 has 43 fractions 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 for order 100 has 3045 fractions -- Farey Sequence for order 200 has 12233 fractions -- Farey Sequence for order 300 has 27399 fractions -- Farey Sequence for order 400 has 48679 fractions -- Farey Sequence for order 500 has 76117 fractions -- Farey Sequence for order 600 has 109501 fractions -- Farey Sequence for order 700 has 149019 fractions -- Farey Sequence for order 800 has 194751 fractions -- Farey Sequence for order 900 has 246327 fractions -- Farey Sequence for order 1000 has 304193 fractions
REXX
<lang rexx>/*REXX program computes & shows a Farey sequence (or the # of fractions)*/ parse arg L H I . /*get optional values from C.L. */ if L== then L=5 /*L not specified? Use default.*/ oldL=L /*original L (negativity=noshow)*/ L=abs(L) /*but ··· use |L| for all else.*/ if H== then H=L /*H not specified? Use default.*/ if I== then I=1 /*I " " " " */
do n=L to H by I /*process range (could be only 1)*/ @=fareyF(n); #=' 'words(@)" " /*go ye forth & compute Farey #s.*/ say center('Farey sequence for order ' n " has" # 'fractions.', 150, '═') if oldL<0 then iterate /*don't show Farey fractions if -*/ say @; say /*show Farey fractions+blank line*/ end /*n*/ /* [↑] build/show Farey fractions*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────FAREYF subroutine───────────────────*/ fareyf: procedure; parse arg x; n.1=0; d.1=1; n.2=1; d.2=x /*kit parts.*/ $=n.1'/'d.1 n.2"/"d.2 /*a starter kit for the Farey seq*/
/* [↓] now, build on the starter*/ do j=1; y=j+1; z=j+2 /*construct from thirds on "up". */ n.z=((d.j+x)%d.y)*n.y-n.j /* " fraction numerator. */ d.z=((d.j+x)%d.y)*d.y-d.j /* " " denominator.*/ if n.z>x then leave /*Should construction be stopped?*/ $=$ n.z'/'d.z /*Heck no, add this to party mix.*/ end /*j*/ /* [↑] construct the Farey seq. */
return $ /*return with the fractions. */</lang> output when using the following for input: 1 11
═══════════════════════════════════════════════════Farey sequence for order 1 has 2 fractions.════════════════════════════════════════════════════ 0/1 1/1 ═══════════════════════════════════════════════════Farey sequence for order 2 has 3 fractions.════════════════════════════════════════════════════ 0/1 1/2 1/1 ═══════════════════════════════════════════════════Farey sequence for order 3 has 5 fractions.════════════════════════════════════════════════════ 0/1 1/3 1/2 2/3 1/1 ═══════════════════════════════════════════════════Farey sequence for order 4 has 7 fractions.════════════════════════════════════════════════════ 0/1 1/4 1/3 1/2 2/3 3/4 1/1 ═══════════════════════════════════════════════════Farey sequence for order 5 has 11 fractions.═══════════════════════════════════════════════════ 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 ═══════════════════════════════════════════════════Farey sequence for order 6 has 13 fractions.═══════════════════════════════════════════════════ 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 ═══════════════════════════════════════════════════Farey sequence for order 7 has 19 fractions.═══════════════════════════════════════════════════ 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 ═══════════════════════════════════════════════════Farey sequence for order 8 has 23 fractions.═══════════════════════════════════════════════════ 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 ═══════════════════════════════════════════════════Farey sequence for order 9 has 29 fractions.═══════════════════════════════════════════════════ 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 ══════════════════════════════════════════════════Farey sequence for order 10 has 33 fractions.═══════════════════════════════════════════════════ 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 ══════════════════════════════════════════════════Farey sequence for order 11 has 43 fractions.═══════════════════════════════════════════════════ 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
output when using the following for input: -100 1000 100
═════════════════════════════════════════════════Farey sequence for order 100 has 3045 fractions.═════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 200 has 12233 fractions.═════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 300 has 27399 fractions.═════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 400 has 48679 fractions.═════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 500 has 76117 fractions.═════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 600 has 109501 fractions.════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 700 has 149019 fractions.════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 800 has 194751 fractions.════════════════════════════════════════════════ ════════════════════════════════════════════════Farey sequence for order 900 has 246327 fractions.════════════════════════════════════════════════ ═══════════════════════════════════════════════Farey sequence for order 10000 has 304193 fractions.════════════════════════════════════════════════