Ciąg Fareya

$N\;$-ty ciąg Fareya $F_N$ to rosnący ciąg liczb wymiernych z przedziału $[0 , 1]$, których mianowniki są nie większe od $N\;$.

Przykłady

• $F_2$ to: $\frac 0 1,\ \frac 1 2,\ \frac 1 1.$
• $F_3$ to: $\frac 0 1,\ \frac 1 3,\ \frac 1 2,\ \frac 2 3,\ \frac 1 1.$
• ciągiem $F_4$ jest: $\frac 0 1,\ \frac 1 4,\ \frac 1 3,\ \frac 1 2,\ \frac 2 3,\ \frac 3 4,\ \frac 1 1.$
• $F_6$ to: $\frac 0 1,\ \frac 1 6,\ \frac 1 5,\ \frac 1 4,\ \frac 1 3,\ \frac 2 5,\ \frac 1 2,\ \frac 3 5,\ \frac 2 3,\ \frac 3 4,\ \frac 4 5,\ \frac 5 6,\ \frac 1 1.$

Konstrukcja

• Napisz ciąg $\frac 0 1,\ \frac 1 1.$
• Tak długo, jak to możliwe wstawiaj pomiędzy liczby $\frac a b, \frac c d$, dla których $b+d\le N\$ liczbę $\frac {a+c}{b+d} \;.$

Własności

• Jeśli liczby $\frac a b$ oraz $\frac{c}{d}$ są kolejnymi liczbami w (dowolnym) ciągu Fareya, to nie ma pomiędzy nimi liczby wymiernej o mianowniku mniejszym niż $b+d\;.$
• Jeśli liczby $\frac a b$ oraz $\frac{c}{d}$ są kolejmymi liczbami w (dowolnym) ciągu Fareya, to $b\cdot c - a\cdot d =1 \;.$

Przykład zastosowania

Znaleźć liczby $m<\sqrt{\frac{1}{2}}<d\,$ najbliższe $\sqrt{\frac{1}{2}}$, których mianowniki są mniejsze od 50.

Mamy:

$\frac 0 1 < \sqrt {\frac 1 2} < \frac 1 1$

czyli

$\frac 0 1 \le m < \sqrt {\frac 1 2} < d \le \frac 1 1$

zachodzi nierówność: $\frac {0+ 1}{1+1} \le m < \sqrt {\frac 1 2}$ więc:

$\frac 1 2 \le m < \sqrt {\frac 1 2} < d \le \frac 1 1$

zauważamy, że skrajne wartości są najlepszymi oszacowaniami spośród liczb o mianowniku nie większym niż 2.

Stwierdzamy, że $\frac {1 +1}{2+1} = \frac 2 3 < \sqrt {\frac 1 2}$ czyli:

$\frac 1 2<\frac 2 3 \le m < \sqrt {\frac 1 2} < d \le \frac 1 1$

a zatem:

$\frac 2 3 \le m < \sqrt {\frac 1 2} < d \le \frac 1 1$

W kolejnych krokach dostajemy:

$\frac 2 3 \le m < \sqrt {\frac 1 2} < d \le \frac 3 4$

$\frac 2 3 \le m < \sqrt {\frac 1 2} < d \le \frac 5 7$

$\frac 7 {10} \le m < \sqrt {\frac 1 2} < d \le \frac 5 7$

$\frac {12} {17} \le m < \sqrt {\frac 1 2} < d \le \frac 5 7$

$\frac {12} {17} \le m < \sqrt {\frac 1 2} < d \le \frac {17}{24}$

$\frac {12}{17} \le m < \sqrt {\frac 1 2} < d \le \frac {29}{41}$

Liczby $\frac {12}{17}$ oraz $\frac{29}{41}$ są kolejnymi liczbami w ciągu Fareya, więc nie ma pomiędzy nimi liczby o mianowniku mniejszym niż 58, czyli są to poszukiwane liczby.

Zobacz też

• Drzewo Sterna-Brocota

Linki zewnętrzne

• Farey Sequence MathWorld (ang.)