Difference between revisions of "Farey sequence"

Latest revision as of 04:16, 30 January 2021

A Farey sequence of order $n$ is the sequence of all completely reduced fractions between 0 and 1 where, when in lowest terms, each fraction has a denominator less than or equal to $n$ . Each fraction starts with 0, denoted by the fraction 0/1, and ends in 1, denoted by the fraction 1/1.

Examples

Farey sequences of orders 1-4 are:

$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\}$

Where $F_n$ denotes a Farey sequence of order $n$ .

Proof Sketch

Which is bigger, $\frac{a}{b}$ or $\frac{a+1}{b+1}$ ?

Which is bigger, $\frac{a}{b}$ or $\frac{a+1}{b+2}$ ?

Do you see a pattern?

Assume $a$ and $b$ are positive.

Properties

Sequence length

A Farey sequence of any order contains all terms in a Farey sequence of lower order. More specifically, $F_n$ contains all the terms in $F_{n-1}$ . Also, $F_n$ contains an extra term for every number less than $n$ relatively prime to $n$ . Thus, we can write

$\#(F_n)=\#(F_{n-1})+\phi{(n)}$

This article is a stub. Help us out by expanding it.

@@ Line 1: / Line 1: @@
-A Farey sequence of order <math>n</math> is the sequence of all completely reduced fractions between 0 and 1 where, when in lowest terms, each fraction has a denominator less than or equal to <math>n</math>. Each fraction starts with 0, denoted by the fraction 0/1, and ends in 1, denoted by the fraction 1/1.
+A '''Farey sequence''' of order <math>n</math> is the sequence of all completely reduced fractions between 0 and 1 where, when in lowest terms, each fraction has a denominator less than or equal to <math>n</math>. Each fraction starts with 0, denoted by the fraction 0/1, and ends in 1, denoted by the fraction 1/1.
+==Examples==
+Farey sequences of orders 1-4 are:
+<math>F_1=\{0/1, 1/1\}</math>
+<math>F_2=\{0/1, 1/2, 1/1\}</math>
+<math>F_3=\{0/1, 1/3, 1/2, 2/3, 1/1\}</math>
+<math>F_4=\{0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1\}</math>
+Where <math>F_n</math> denotes a Farey sequence of order <math>n</math>.
+==Proof Sketch==
+Which is bigger, <math>\frac{a}{b}</math> or <math>\frac{a+1}{b+1}</math>?
+Which is bigger, <math>\frac{a}{b}</math> or <math>\frac{a+1}{b+2}</math>?
+Do you see a pattern?
+Assume <math>a</math> and <math>b</math> are positive.
+==Properties==
+===Sequence length===
+A Farey sequence of any order contains all terms  in a Farey sequence of lower order. More specifically, <math>F_n</math> contains all the terms in <math>F_{n-1}</math>. Also, <math>F_n</math> contains an extra term for every number less than <math>n</math> relatively prime to <math>n</math>. Thus, we can write
+<math>\#(F_n)=\#(F_{n-1})+\phi{(n)}</math>
 {{stub}}

Page

Toolbox

Search