Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Simple continued fraction
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Formulation == A continued fraction in canonical form is an expression of the form :<math>a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \vphantom{\cfrac11} {_\ddots}}}}</math> where ''a<sub>i</sub>'' are integer numbers, called the ''coefficients'' or ''terms'' of the continued fraction.{{sfn|Pettofrezzo|Byrkit|1970|p=150}} When the expression contains finitely many terms, it is called a ''finite'' continued fraction. When the expression contains infinitely many terms, it is called an ''infinite'' continued fraction.{{sfn|Collins|2001}} When the terms eventually repeat from some point onwards, the continued fraction is called ''[[periodic continued fraction|periodic]]''.{{sfn|Weisstein|2022}} Thus, all of the following illustrate valid finite simple continued fractions: {| class="wikitable" |+Examples of finite simple continued fractions !Formula !Numeric !Remarks |- |<math>\ a_0</math> |<math>\ 2</math> |All integers are a [[degenerate case]] |- |<math>\ a_0 + \cfrac{1}{a_1}</math> |<math>\ 2 + \cfrac{1}{3}</math> |Simplest possible fractional form |- |<math>\ a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}}</math> |<math>\ -3 + \cfrac{1}{2 + \cfrac{1}{18}}</math> |First integer may be negative |- |<math>\ a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3}}}</math> |<math>\ \cfrac{1}{15 + \cfrac{1}{1 + \cfrac{1}{102}}}</math> |First integer may be zero |} For simple continued fractions of the form : <math>r=a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \vphantom{\cfrac11} {_\ddots}}}}</math> the <math>a_n</math> term can be calculated from the following recursive sequence: <math>f_{n+1} = \frac{1}{f_n - \lfloor f_n \rfloor}</math> where <math>f_0 = r </math> and <math>a_n= \left \lfloor f_n \right \rfloor</math>. from which it can be understood that the <math>a_n</math> sequence stops if <math>f_n = \lfloor f_n \rfloor</math> is an integer. ===Notations=== Consider a continued fraction expressed as :<math>x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4}}}}</math> Because such a continued fraction expression may take a significant amount of vertical space, a number of methods have been tried to shrink it. [[Gottfried Wilhelm Leibniz|Gottfried Leibniz]] sometimes used the notation<ref>{{cite journal |last=Cajori |first=Florian |author-link=Florian Cajori |year=1925 |title=Leibniz, the Master-Builder of Mathematical Notations |journal=Isis |volume=7 |number=3 |pages=412–429 |doi=10.1086/358328 |doi-access=free }}</ref> <!-- very hacky workaround; mediawiki latex doesn't have good support for vertical alignment commands --> :<math> \begin{align}x = a_0 + \dfrac{1}{a_1} {{}\atop+} \\[28mu]\ \end{align} \! \begin{align} \dfrac{1}{a_2} {{}\atop+} \\[2mu] \ \end{align} \! \begin{align}\dfrac{1}{a_3} {{}\atop+}\end{align} \! \begin{align}\\[2mu] \dfrac{1}{a_4},\end{align} </math> and later the same idea was taken even further with the nested fraction bars drawn aligned, for example by [[Alfred Pringsheim]] as :<math> x = a_0 + {{}\atop{\big|\!}}\! \frac{1}{\,a_1} \!{{\!\big|}\atop{}} + {{}\atop{\big|\!}}\! \frac{1}{\,a_2} \!{{\!\big|}\atop{}} + {{}\atop{\big|\!}}\! \frac{1}{\,a_3} \!{{\!\big|}\atop{}} + {{}\atop{\big|\!}}\! \frac{1}{\,a_4} \!{{\!\big|}\atop{}},</math> <!-- simpler coded alternative which doesn't look as good (though both are somewhat hacky): :<math> x = a_0 + \frac{\ \ 1 \ \mid}{\mid\,a_1} + \frac{\ \ 1\,\mid}{\mid\,a_2} + \frac{\ \ 1\,\mid}{\mid\,a_3} + \frac{\ \ 1\,\mid}{\mid\,a_4},</math> --> or in more common related notations as<ref>{{cite book |last=Swanson |first=Ellen |year=1999 |orig-year=1971 |title=Mathematics into Type |edition=Updated |publisher=American Mathematical Society |others=Updated by O'Sean, Arlene; Schleyer, Antoinette |url=https://www.ams.org/publications/authors/mit-2.pdf |at=2.4.1c "Continued fractions", {{pgs|18}}}}</ref> :<math> x = a_0 + {1 \over a_1 +}\, {1 \over a_2 +}\, {1 \over a_3 +}\, {1 \over a_4} </math> or :<math> x = a_0 + {1 \over a_1} {{}\atop+} {1 \over a_2} {{}\atop+} {1 \over a_3} {{}\atop+} {1 \over a_4}. </math> [[Carl Friedrich Gauss]] used a notation reminiscent of [[Summation#Capital-sigma notation|summation notation]], :<math>x = a_0 + \underset{i=1}{\overset{4}{\mathrm K}} ~ \frac{1}{a_i}, </math> or in cases where the numerator is always 1, eliminated the fraction bars altogether, writing a list-style :<math>x = [a_0; a_1, a_2, a_3, a_4]. </math> Sometimes list-style notation uses angle brackets instead, :<math>x = \left\langle a_0; a_1, a_2, a_3, a_4 \right\rangle.</math> The semicolon in the square and angle bracket notations is sometimes replaced by a comma.{{sfn|Long|1972|p=173}}{{sfn|Pettofrezzo|Byrkit|1970|p=152}} One may also define ''infinite simple continued fractions'' as [[limit of a sequence|limits]]: :<math>[a_0; a_1, a_2, a_3, \,\ldots\, ] = \lim_{n \to \infty}\, [a_0; a_1, a_2, \,\ldots, a_n]. </math> This limit exists for any choice of <math>a_0</math> and positive integers <math>a_1,a_2,\ldots</math>.{{sfn|Long|1972|p=183}}{{sfn|Pettofrezzo|Byrkit|1970|p=158}} ==Calculating continued fraction representations== Consider a real number {{tmath|r}}. Let <math>i=\lfloor r \rfloor </math> and let {{tmath|1=f = r - i}}. When {{tmath|f\neq 0}}, the continued fraction representation of <math>r</math> is {{tmath|[i;a_1,a_2,\ldots]}}, where <math>[a_1;a_2,\ldots]</math> is the continued fraction representation of {{tmath|1/f}}. When {{tmath|r\geq 0}}, then <math>i</math> is the [[integer part]] of <math>r</math>, and <math>f</math> is the [[fractional part]] of {{tmath|r}}. In order to calculate a continued fraction representation of a number <math>r</math>, write down the [[Floor function|floor]] of <math>r</math>. Subtract this value from <math>r</math>. If the difference is 0, stop; otherwise find the [[multiplicative inverse|reciprocal]] of the difference and repeat. The procedure will halt if and only if <math>r</math> is rational. This process can be efficiently implemented using the [[Euclidean algorithm]] when the number is rational. The table below shows an implementation of this procedure for the number {{tmath|1= 3.245 = 649/200 }}: :{| class="wikitable" |- !Step !Real<br />Number !Integer<br />part !Fractional<br />part !Simplified !Reciprocal<br />of {{mvar|f}} |- !1 |<math>r = \frac{649}{200}</math> |<math>i = 3</math> |<math>f = \frac{649}{200} - 3 </math> |<math>= \frac{49}{200}</math> |<math>\frac{1}{f} = \frac{200}{49} </math> |- !2 |<math>r = \frac{200}{49} </math> |<math>i = 4</math> |<math>f = \frac{200}{49} - 4 </math> |<math> = \frac{4}{49} </math> |<math> \frac{1}{f} = \frac{49}{4} </math> |- !3 |<math>r = \frac{49}{4} </math> |<math>i = 12</math> |<math>f = \frac{49}{4} - 12 </math> |<math>= \frac{1}{4} </math> |<math>\frac{1}{f} = \frac{4}{1} </math> |- !4 |<math>r = 4</math> |<math>i = 4 </math> |<math>f = 4 - 4 </math> |<math>= 0 </math> |colspan="2"|'''STOP''' |} The continued fraction for {{tmath|3.245}} is thus <math>[3; 4,12,4],</math> or, expanded: <math display=block> \frac{649}{200} = 3 + \cfrac{1}{4 + \cfrac{1}{12 + \cfrac{1}{4}}}. </math> ==Reciprocals== The continued fraction representations of a positive rational number and its [[multiplicative inverse|reciprocal]] are identical except for a shift one place left or right depending on whether the number is less than or greater than one respectively. In other words, the numbers represented by <math>[a_0;a_1,a_2,\ldots,a_n]</math> and <math>[0;a_0,a_1,\ldots,a_n]</math> are reciprocals. For instance if <math>a</math> is an integer and <math>x < 1</math> then :<math>x=0 + \frac{1}{a + \frac{1}{b}}</math> and <math>\frac{1}{x} = a + \frac{1}{b}</math>. If <math>x>1</math> then :<math>x = a + \frac{1}{b}</math> and <math>\frac{1}{x} = 0 + \frac{1}{a + \frac{1}{b}}</math>. The last number that generates the remainder of the continued fraction is the same for both <math>x</math> and its reciprocal. For example, :<math>2.25 = \frac{9}{4} = [2;4]</math> and <math>\frac{1}{2.25} = \frac{4}{9} = [0;2,4]</math>. ==Finite continued fractions==<!-- This section is linked from [[Continued fraction]] --> Every finite continued fraction represents a [[rational number]], and every rational number can be represented in precisely two different ways as a finite continued fraction, with the conditions that the first coefficient is an integer and the other coefficients are positive integers. These two representations agree except in their final terms. In the longer representation the final term in the continued fraction is 1; the shorter representation drops the final 1, but increases the new final term by 1. The final element in the short representation is therefore always greater than 1, if present. In symbols: :{{math|[''a''{{sub|0}}; ''a''{{sub|1}}, ''a''{{sub|2}}, ..., ''a''{{sub|''n'' − 1}}, ''a''{{sub|''n''}}, 1] {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ''a''{{sub|2}}, ..., ''a''{{sub|''n'' − 1}}, ''a''{{sub|''n''}} + 1]}}. :{{math|[''a''{{sub|0}}; 1] {{=}} [''a''{{sub|0}} + 1]}}. == Infinite continued fractions and convergents {{anchor|Convergents}} == [[File:Golden ration convergents.svg|thumb|Convergents approaching the [[golden ratio]]]] Every infinite continued fraction is [[irrational number|irrational]], and every irrational number can be represented in precisely one way as an infinite continued fraction. An infinite continued fraction representation for an irrational number is useful because its initial segments provide rational approximations to the number. These rational numbers are called the '''convergents''' of the continued fraction.{{sfn|Long|1972|p=177}}{{sfn|Pettofrezzo|Byrkit|1970|pp=162–163}} The larger a term is in the continued fraction, the closer the corresponding convergent is to the irrational number being approximated. Numbers like π have occasional large terms in their continued fraction, which makes them easy to approximate with rational numbers. Other numbers like ''e'' have only small terms early in their continued fraction, which makes them more difficult to approximate rationally. The [[golden ratio]] φ has terms equal to 1 everywhere—the smallest values possible—which makes φ the most difficult number to approximate rationally. In this sense, therefore, it is the "most irrational" of all irrational numbers. Even-numbered convergents are smaller than the original number, while odd-numbered ones are larger. For a continued fraction {{math|[''a''{{sub|0}}; ''a''{{sub|1}}, ''a''{{sub|2}}, ...]}}, the first four convergents (numbered 0 through 3) are :<math> \frac{a_0}{1},\, \frac{a_1a_0 + 1}{a_1},\, \frac{a_2(a_1a_0 + 1) + a_0}{a_2a_1 + 1},\, \frac{a_3\bigl(a_2(a_1a_0 + 1) + a_0\bigr) + (a_1a_0 + 1)}{a_3(a_2a_1 + 1) + a_1}. </math> The numerator of the third convergent is formed by multiplying the numerator of the second convergent by the third coefficient, and adding the numerator of the first convergent. The denominators are formed similarly. Therefore, each convergent can be expressed explicitly in terms of the continued fraction as the ratio of certain [[multivariate polynomial]]s called ''[[Continuant (mathematics)|continuants]]''. If successive convergents are found, with numerators {{mvar|h}}{{sub|1}}, {{mvar|h}}{{sub|2}}, ... and denominators {{mvar|k}}{{sub|1}}, {{mvar|k}}{{sub|2}}, ... then the relevant recursive relation is that of [[Gaussian brackets]]: :<math>\begin{align} h_n &= a_nh_{n-1} + h_{n-2}, \\[3mu] k_n &= a_nk_{n-1} + k_{n-2}. \end{align}</math> The successive convergents are given by the formula :<math>\frac{h_n}{k_n} = \frac{a_nh_{n-1} + h_{n-2}}{a_nk_{n-1} + k_{n-2}}.</math> Thus to incorporate a new term into a rational approximation, only the two previous convergents are necessary. The initial "convergents" (required for the first two terms) are <sup>0</sup>⁄<sub>1</sub> and <sup>1</sup>⁄<sub>0</sub>. For example, here are the convergents for [0;1,5,2,2]. :{| class="wikitable" |- align="right" ! {{mvar|n}} | −2|| −1|| 0 || 1 || 2 || 3 || 4 |- align="right" ! {{math|''a''{{sub|''n''}}}} | || || 0 || 1 || 5 || 2 || 2 |- align="right" ! {{math|''h''{{sub|''n''}}}} | 0 || 1 || 0 || 1 || 5 || 11 || 27 |- align="right" ! {{math|''k''{{sub|''n''}}}} | 1 || 0 || 1 || 1 || 6 || 13 || 32 |} When using the [[Methods of computing square roots#Heron's method|Babylonian method]] to generate successive approximations to the square root of an integer, if one starts with the lowest integer as first approximant, the rationals generated all appear in the list of convergents for the continued fraction. Specifically, the approximants will appear on the convergents list in positions 0, 1, 3, 7, 15, ... , {{math|2<sup>''k''</sup>−1}}, ... For example, the continued fraction expansion for [[square root of 3|<math>\sqrt3</math>]] is {{math|[1; 1, 2, 1, 2, 1, 2, 1, 2, ...]}}. Comparing the convergents with the approximants derived from the Babylonian method: :{| class="wikitable" |- align="right" ! {{mvar|n}} | −2|| −1|| '''0''' || '''1''' || 2 || '''3''' || 4 || 5 || 6 || '''7''' |- align="right" ! {{math|''a''{{sub|''n''}}}} | || || 1 || 1 || 2 || 1 || 2 || 1 || 2 || 1 |- align="right" ! {{math|''h''{{sub|''n''}}}} | 0 || 1 || '''1''' || '''2''' || 5 || '''7''' || 19 || 26 || 71 || '''97''' |- align="right" ! {{math|''k''{{sub|''n''}}}} | 1 || 0 || '''1''' || '''1''' || 3 || '''4''' || 11 || 15 || 41 || '''56''' |} :{{math|''x''{{sub|0}} {{=}} 1 {{=}} {{sfrac|1|1}}}} :{{math|''x''{{sub|1}} {{=}} {{sfrac|1|2}}(1 + {{sfrac|3|1}}) {{=}} {{sfrac|2|1}} {{=}} 2}} :{{math|''x''{{sub|2}} {{=}} {{sfrac|1|2}}(2 + {{sfrac|3|2}}) {{=}} {{sfrac|7|4}}}} :{{math|''x''{{sub|3}} {{=}} {{sfrac|1|2}}({{sfrac|7|4}} + {{sfrac|3|{{sfrac|7|4}}}}) {{=}} {{sfrac|97|56}}}} ===Properties=== The [[Baire space (set theory)|Baire space]] is a topological space on infinite sequences of natural numbers. The infinite continued fraction provides a [[homeomorphism]] from the Baire space to the space of irrational real numbers (with the subspace topology inherited from the [[Euclidean topology|usual topology]] on the reals). The infinite continued fraction also provides a map between the [[quadratic irrational]]s and the [[dyadic rational]]s, and from other irrationals to the set of infinite strings of binary numbers (i.e. the [[Cantor set]]); this map is called the [[Minkowski question-mark function]]. The mapping has interesting self-similar [[fractal]] properties; these are given by the [[modular group]], which is the subgroup of [[Möbius transformation]]s having integer values in the transform. Roughly speaking, continued fraction convergents can be taken to be Möbius transformations acting on the (hyperbolic) [[upper half-plane]]; this is what leads to the fractal self-symmetry. The limit probability distribution of the coefficients in the continued fraction expansion of a random variable uniformly distributed in (0, 1) is the [[Gauss–Kuzmin distribution]]. ===Some useful theorems=== If <math>\ a_0\ ,</math> <math>a_1\ ,</math> <math>a_2\ ,</math> <math>\ \ldots\ </math> is an infinite sequence of positive integers, define the sequences <math>\ h_n\ </math> and <math>\ k_n\ </math> recursively: {| border="0" cellpadding="5" cellspacing="10" align="none" |- |<math> h_{n} = a_n\ h_{n-1} + h_{n-2}\ ,</math> | | |<math> h_{-1} = 1\ ,</math> | |<math> h_{-2} = 0\ ;</math> |- |<math> k_{n}= a_n\ k_{n-1} + k_{n-2}\ ,</math> | | |<math> k_{-1} = 0\ ,</math> | |<math> k_{-2} = 1 ~.</math> |} <blockquote>'''Theorem 1.''' For any positive real number <math>\ x\ </math> :<math> \left[\ a_0;\ a_1,\ \dots, a_{n-1}, x\ \right]=\frac{x\ h_{n-1} + h_{n-2}}{\ x\ k_{n-1} + k_{n-2}\ }, \quad \left[\ a_0;\ a_1,\ \dots, a_{n-1} + x\ \right]=\frac{h_{n-1} + xh_{n-2}}{\ k_{n-1} + x k_{n-2}\ }</math> </blockquote> <blockquote>'''Theorem 2.''' The convergents of <math>\ [\ a_0\ ;</math> <math>a_1\ ,</math> <math>a_2\ ,</math> <math>\ldots\ ]\ </math> are given by :<math>\left[\ a_0;\ a_1,\ \dots, a_n\ \right] = \frac{h_n}{\ k_n\ } ~.</math> or in matrix form,<math display="block">\begin{bmatrix} h_n & h_{n-1} \\ k_n & k_{n-1} \end{bmatrix} = \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix}</math> '''Theorem 3.''' If the <math>\ n</math>th convergent to a continued fraction is <math>\ \frac{ h_n}{ k_n }\ ,</math> then :<math> k_n\ h_{n-1} - k_{n-1}\ h_n = (-1)^n\ ,</math> or equivalently :<math> \frac{ h_n }{\ k_n\ } - \frac{ h_{n-1} }{\ k_{n-1}\ } = \frac{ (-1)^{n+1} }{\ k_{n-1}\ k_n\ } ~.</math> </blockquote> '''Corollary 1:''' Each convergent is in its lowest terms (for if <math>\ h_n\ </math> and <math>\ k_n\ </math> had a nontrivial common divisor it would divide <math>\ k_n\ h_{n-1} - k_{n-1}\ h_n\ ,</math> which is impossible). '''Corollary 2:''' The difference between successive convergents is a fraction whose numerator is unity: :<math> \frac{h_n}{k_n} - \frac{ h_{n-1} }{ k_{n-1} } = \frac{\ h_n\ k_{n-1} - k_n\ h_{n-1}\ }{\ k_n\ k_{n-1}\ } = \frac{ (-1)^{n+1} }{\ k_n\ k_{n-1}\ } ~.</math> '''Corollary 3:''' The continued fraction is equivalent to a series of alternating terms: :<math>a_0 + \sum_{n=0}^\infty \frac{ (-1)^n }{\ k_{n}\ k_{n+1}\ } ~.</math> '''Corollary 4:''' The matrix :<math>\begin{bmatrix} h_n & h_{n-1} \\ k_n & k_{n-1} \end{bmatrix} = \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix}</math> has [[determinant]] <math>(-1)^{n+1}</math>, and thus belongs to the group of <math>\ 2\times 2\ </math> [[unimodular matrix|unimodular matrices]] <math>\ \mathrm{GL}(2,\mathbb{Z}) ~.</math> '''Corollary 5:''' The matrix<math display="block">\begin{bmatrix} h_n & h_{n-2} \\ k_n & k_{n-2} \end{bmatrix} = \begin{bmatrix} h_{n-1} & h_{n-2} \\ k_{n-1} & k_{n-2} \end{bmatrix} \begin{bmatrix} a_{n} & 0 \\ 1 & 1 \end{bmatrix}</math> has determinant <math>(-1)^na_n</math>, or equivalently,<math display="block"> \frac{ h_n }{\ k_n\ } - \frac{ h_{n-2} }{\ k_{n-2}\ } = \frac{ (-1)^{n} }{\ k_{n-2 }\ k_n\ }a_n</math>meaning that the odd terms monotonically decrease, while the even terms monotonically increase. '''Corollary 6:''' The denominator sequence <math>k_0, k_1, k_2, \dots</math> satisfies the recurrence relation <math>k_{-1} = 0, k_0 = 1, k_n = k_{n-1}a_n + k_{n-2}</math>, and grows at least as fast as the [[Fibonacci sequence]], which itself grows like <math>O(\phi^n)</math> where <math>\phi= 1.618\dots</math> is the [[golden ratio]]. <blockquote>'''Theorem 4.''' Each (<math>\ s</math>th) convergent is nearer to a subsequent (<math>\ n</math>th) convergent than any preceding (<math>\ r</math>th) convergent is. In symbols, if the <math>\ n</math>th convergent is taken to be <math>\ \left[\ a_0;\ a_1,\ \ldots,\ a_n\ \right] = x_n\ ,</math> then :<math> \left|\ x_r - x_n\ \right| > \left|\ x_s - x_n\ \right| </math> for all <math>\ r < s < n ~.</math> </blockquote> '''Corollary 1:''' The even convergents (before the <math>\ n</math>th) continually increase, but are always less than <math>\ x_n ~.</math> '''Corollary 2:''' The odd convergents (before the <math>\ n</math>th) continually decrease, but are always greater than <math>\ x_n ~.</math> <blockquote>'''Theorem 5.''' :<math>\frac{1}{\ k_n\ (k_{n+1} + k_n)\ } < \left|\ x - \frac{ h_n }{\ k_n\ }\ \right| < \frac{1}{\ k_n\ k_{n+1}\ } ~.</math> </blockquote> '''Corollary 1:''' A convergent is nearer to the limit of the continued fraction than any fraction whose denominator is less than that of the convergent. '''Corollary 2:''' A convergent obtained by terminating the continued fraction just before a large term is a close approximation to the limit of the continued fraction.<blockquote>'''Theorem 6:''' Consider the set of all open intervals with end-points <math>[0;a_1, \dots, a_n], [0;a_1, \dots, a_n+1]</math>. Denote it as <math>\mathcal C</math>. Any open subset of <math>[0, 1] \setminus \Q</math> is a disjoint union of sets from <math>\mathcal C</math>.</blockquote>'''Corollary:''' The infinite continued fraction provides a homeomorphism from the Baire space to <math>[0, 1] \setminus \Q</math>.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)