Difference between revisions of "Farey sequence"
(→Proof Sketch: assume positive) |
|||
(6 intermediate revisions by 4 users not shown) | |||
Line 12: | Line 12: | ||
<math>F_4=\{0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 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 | + | 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== | ==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 | 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> | + | <math>\#(F_n)=\#(F_{n-1})+\phi{(n)}</math> |
+ | |||
+ | |||
+ | |||
{{stub}} | {{stub}} |
Latest revision as of 03:16, 30 January 2021
A Farey sequence of order 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 . 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:
Where denotes a Farey sequence of order .
Proof Sketch
Which is bigger, or ?
Which is bigger, or ?
Do you see a pattern?
Assume and are positive.
Properties
Sequence length
A Farey sequence of any order contains all terms in a Farey sequence of lower order. More specifically, contains all the terms in . Also, contains an extra term for every number less than relatively prime to . Thus, we can write
This article is a stub. Help us out by expanding it.