Difference between revisions of "Farey sequence"
(New page: 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...) |
|||
| 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>. | ||
| + | |||
| + | ==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}} | {{stub}} | ||
Revision as of 13:34, 31 August 2008
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 .
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
$#(F_n)=#(F_{n-1})+\phi{n}$ (Error compiling LaTeX. Unknown error_msg) This article is a stub. Help us out by expanding it.
