Farey sequence
- Farey sequence
(sometimes incorrectly called a Farey series.)
- definition
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.
Each Farey sequence starts with value 0, denoted by the fraction and ends with the value 1, denoted by the fraction .
The Farey sequences of orders 1 to 5 are:
- F1 =
- F2 =
- F3 =
- F4 =
- F5 =
- task requirements
- compute and show the Farey sequence for order 1 through 11 (inclusive).
- compute and display the number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds.
- see also
- sequence A006842 numerators of Farey series of order 1, 2, ··· on OEIS, The On-line Encyclopedia of Integer Sequences (R).
- sequence A006843 denominators of Farey series of order 1, 2, ··· on OEIS, The On-line Encyclopedia of Integer Sequences (R).
- sequence A005728 number of fractions in Farey series of order n. on OEIS, The On-line Encyclopedia of Integer Sequences (R).
- entry Farey sequence on Wolfram Mathworld (TM).
- Wiki Farey sequence in Wikipedia.
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*/ {
auto res = [RationalT!int(0, 1)]; foreach (immutable k; 1 .. n + 1) res ~= iota(1, k + 1).map!(m => RationalT!int(m, k)).array; return res.sort().uniq;
}
long fareyLen(in long n) pure nothrow {
return (n * (n+3)) / 2 - iota(2, n+1).map!(k => fareyLen(n/k)).sum;
}
void main() {
writefln("Farey sequence for order 1 through 11:\n%(%s\n%)", iota(1, 12).map!farey); writeln("\nNumber of fractions in the Farey sequence " "for order 100 through 1000 by hundreds:\n", iota(100, 1_001, 100).map!fareyLen);
}</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] Number of fractions in the Farey sequence for order 100 through 1000 by hundreds: [3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193]
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.════════════════════════════════════════════════