Ułamek łańcuchowy

Ułamek łańcuchowy, ułamek ciągły^[1] (skończony) to wyrażenie postaci:

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\stackrel {\ddots }{\qquad a_{k-2}+{\cfrac {1}{a_{k-1}+{\cfrac {1}{a_{k}}}}}}}}}}}}}$

gdzie ${\displaystyle a_{0}}$ jest liczbą całkowitą, a wszystkie pozostałe liczby ${\displaystyle a_{n}}$ są naturalne i dodatnie. Liczby ${\displaystyle a_{1},a_{2},\dots ,a_{k}}$ nazywamy mianownikami częściowymi ułamka łańcuchowego. W niektórych źródłach zezwala się, by liczby ${\displaystyle a_{n}}$ były rzeczywiste, a ułamki, w których ${\displaystyle a_{0}\in \mathbb {Z} }$ i ${\displaystyle a_{1},\dots ,a_{k}\in \mathbb {N} _{+}}$, nazywa się dodatkowo arytmetycznymi.^[2]

Zamiast powyższej „piętrowej” notacji ułamki łańcuchowe najczęściej zapisuje się w postaci ciągu ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ,a_{k}].}$ Spotykane są również inne notacje, między innymi notacja wprowadzona przez Pringsheima:

${\displaystyle a_{0}+{\frac {\ 1\mid }{\mid a_{1}\ }}+{\frac {\ 1\mid }{\mid a_{2}\ }}+{\frac {\ 1\mid }{\mid a_{3}\ }}+\ldots }$.

Ułamek łańcuchowy nieskończony definiujemy jako granicę ciągu ułamków skończonych (granica ta zawsze istnieje):

${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]=\lim _{k\to \infty }[a_{0};a_{1},a_{2},a_{3},\dots ,a_{k}].}$

Każdą liczbę rzeczywistą można zapisać w postaci ułamka łańcuchowego. Liczbom wymiernym odpowiadają ułamki skończone, natomiast liczbom niewymiernym – ułamki nieskończone.^[3] Dla ułamków łańcuchowych skończonych reprezentujących liczby wymierne zachodzi

${\displaystyle [a_{0};a_{1},a_{2},\dots ,a_{k}+1]=[a_{0};a_{1},a_{2},\dots ,a_{k},1],}$

czyli ich rozwinięcie w ułamek łańcuchowy nie jest jednoznaczne. Staje się ono jednoznaczne przy założeniu, że ta ostatnia liczba jest większa od 1, tzn. każdą liczbę wymierną można jednoznacznie przedstawić w postaci ${\displaystyle [a_{0};a_{1},a_{2},\dots ,a_{k}],}$ gdzie ${\displaystyle a_{0}}$ jest liczbą całkowitą, ${\displaystyle a_{1},\dots ,a_{k}}$ są liczbami naturalnymi, a ${\displaystyle a_{k}>1.}$ Rozwinięcie liczby niewymiernej w (nieskończony) ułamek łańcuchowy zawsze jest jednoznaczne.^[3]

Każdy okresowy ułamek łańcuchowy przedstawia pewną niewymierność kwadratową, tzn. niewymierny pierwiastek równania kwadratowego o współczynnikach całkowitych. Każda niewymierność kwadratowa rozwija się w okresowy arytmetyczny ułamek łańcuchowy.^[3]

Algorytm znajdowania reprezentacji liczby ${\displaystyle x}$ w postaci ułamka łańcuchowego można opisać następująco:

1. ${\displaystyle r=x,\,n=0}$
2. ${\displaystyle a_{n}=\lfloor r\rfloor }$
3. JEŚLI ${\displaystyle r-a_{n}=0}$ – STOP
4. ${\displaystyle r=1/(r-a_{n}),\,n=n+1}$
5. PRZEJDŹ DO 2

Dla ${\displaystyle x=2{,}35}$ otrzymujemy na przykład:

• ${\displaystyle r=2{,}35={\frac {47}{20}}}$
• ${\displaystyle a_{0}=\lfloor r\rfloor =2}$
• ${\displaystyle r={\frac {1}{{\frac {47}{20}}-2}}={\frac {20}{7}}}$
• ${\displaystyle a_{1}=\lfloor r\rfloor =2}$
• ${\displaystyle r={\frac {1}{{\frac {20}{7}}-2}}={\frac {7}{6}}}$
• ${\displaystyle a_{2}=\lfloor r\rfloor =1}$
• ${\displaystyle r={\frac {1}{{\frac {7}{6}}-1}}=6}$
• ${\displaystyle a_{3}=\lfloor r\rfloor =6}$

Zatem:

${\displaystyle 2{,}35=2+{\cfrac {1}{2+{\cfrac {1}{1+{\cfrac {1}{6}}}}}}=[2;2,1,6]}$

Niech ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]}$ będzie ułamkiem łańcuchowym (skończonym lub nieskończonym), wówczas liczbę ${\displaystyle [a_{0};a_{1},a_{2},\dots ,a_{n}]}$ nazywamy ${\displaystyle n}$-tym reduktem tego ułamka łańcuchowego.^[2]

Dla ${\displaystyle p_{n},q_{n}}$ zdefiniowanych rekurencyjnie wzorami:

${\displaystyle p_{-1}=1,\,q_{-1}=0,\,p_{0}=a_{0},\,q_{0}=1}$

${\displaystyle p_{k+1}=a_{k+1}p_{k}+p_{k-1}}$

${\displaystyle q_{k+1}=a_{k+1}q_{k}+q_{k-1}}$

zachodzi ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ,a_{n}]={\frac {p_{n}}{q_{n}}}.}$^[2][3] Ponadto jest to postać nieskracalna tego ułamka.^[2]

Kolejne redukty rozwinięcia danej liczby w ułamek łańcuchowy są najlepszymi przybliżeniami wymiernymi tej liczby o możliwie małych mianownikach. Dokładniej, jeżeli ułamek ${\displaystyle {\frac {p_{n}}{q_{n}}}}$ jest ${\displaystyle n}$-tym reduktem rozwinięcia liczby ${\displaystyle a\in \mathbb {R} }$ w ułamek łańcuchowy, to dla każdej liczby wymiernej ${\displaystyle {\frac {p}{q}}}$ spełniającej warunek ${\displaystyle 0<q<q_{n}}$ zachodzi nierówność

${\displaystyle \left\vert a-{\frac {p_{n}}{q_{n}}}\right\vert <\left\vert a-{\frac {p}{q}}\right\vert }$.^[2]

Ponadto redukty parzyste przybliżają liczbę od dołu (z niedomiarem), a nieparzyste od góry (z nadmiarem).^[2][3]

• stała Chinczyna
• Równanie Pella

• Władysław Narkiewicz: Teoria liczb. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, s. 271–285.

• Ułamki Łańcuchowe, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 2 października 2017 [dostęp 2024-09-04].
• Ułamki łańcuchowe – inny sposób zapisu liczb, blog beta-iks.pl, 19 sierpnia 2021 [dostęp 2023-07-08].
• Eric W.E.W. Weisstein Eric W.E.W., Continued Fraction, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).