Ciąg Fareya

Z Wikipedii

$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\;$ .

Spis treści

1 Przykłady
2 Konstrukcja
3 Własności
4 Przykład zastosowania
5 Zobacz też

[edytuj] 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.$

[edytuj] 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} \;.$

[edytuj] 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 \;.$

[edytuj] 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 3 4$

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

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

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

Liczby $\frac {24}{34}$ oraz $\frac{17}{24}$ 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.