A simple or regular continued fraction is a continued fraction with numerators all equal to one, and denominators built from a sequence { a i } {\displaystyle \{a_{i}\}} of integer numbers. The sequence can be finite or infinite, resulting in a finite (or terminated) continued fraction like
a 0 + 1 a 1 + 1 a 2 + 1 ⋱ + 1 a n {\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{n}}}}}}}}}}
of integer numbers. The sequence can be finite or infinite, resulting in a finite (or terminated) continued fraction like
or an infinite continued fraction like
a 0 + 1 a 1 + 1 a 2 + 1 ⋱ . {\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots }}}}}}.}
Typically, such a continued fraction is obtained through a recursive process which starts by representing a number as the sum of its integer part and its fractional part. The integer is recorded and the reciprocal of the fractional part is then recursively represented by another continued fraction. In the finite case, the recursion is stopped after finitely many steps by using an integer in lieu of another continued fraction. In contrast, an infinite continued fraction is an infinite expression. In either case, all integers in the sequence, other than the first, must be positive. The integers a i {\displaystyle a_{i}} are called the coefficients or terms of the continued fraction.[1]
are called the coefficients or terms of the continued fraction.[1]
Simple continued fractions he a number of remarkable properties related to the Euclidean algorithm for integers or real numbers. Every rational number p {\displaystyle p} / q {\displaystyle q} has two closely related expressions as a finite continued fraction, whose coefficients ai can be determined by applying the Euclidean algorithm to ( p , q ) {\displaystyle (p,q)} . The numerical value of an infinite continued fraction is irrational; it is defined from its infinite sequence of integers as the limit of a sequence of values for finite continued fractions. Each finite continued fraction of the sequence is obtained by using a finite prefix of the infinite continued fraction's defining sequence of integers. Moreover, every irrational number α {\displaystyle \alpha } is the value of a unique infinite regular continued fraction, whose coefficients can be found using the non-terminating version of the Euclidean algorithm applied to the incommensurable values α {\displaystyle \alpha } and 1. This way of expressing real numbers (rational and irrational) is called their continued fraction representation.
Motivation and notation[edit]
/
q
{\displaystyle q}
has two closely related expressions as a finite continued fraction, whose coefficients ai can be determined by applying the Euclidean algorithm to
(
p
,
q
)
{\displaystyle (p,q)}
. The numerical value of an infinite continued fraction is irrational; it is defined from its infinite sequence of integers as the limit of a sequence of values for finite continued fractions. Each finite continued fraction of the sequence is obtained by using a finite prefix of the infinite continued fraction's defining sequence of integers. Moreover, every irrational number
α
{\displaystyle \alpha }
is the value of a unique infinite regular continued fraction, whose coefficients can be found using the non-terminating version of the Euclidean algorithm applied to the incommensurable values
α
{\displaystyle \alpha }
Consider, for example, the rational number 415/93, which is around 4.4624. As a first approximation, start with 4, which is the integer part; 415/93 = 4 + 43/93. The fractional part is the reciprocal of 93/43 which is about 2.1628. Use the integer part, 2, as an approximation for the reciprocal to obtain a second approximation of 4 + 1/2 = 4.5. Now, 93/43 = 2 + 7/43; the remaining fractional part, 7/43, is the reciprocal of 43/7, and 43/7 is around 6.1429. Use 6 as an approximation for this to obtain 2 + 1/6 as an approximation for 93/43 and 4 + 1/2 + 1/6, about 4.4615, as the third approximation. Further, 43/7 = 6 + 1/7. Finally, the fractional part, 1/7, is the reciprocal of 7, so its approximation in this scheme, 7, is exact (7/1 = 7 + 0/1) and produces the exact expression 4 + 1 2 + 1 6 + 1 7 {\displaystyle 4+{\cfrac {1}{2+{\cfrac {1}{6+{\cfrac {1}{7}}}}}}} for 415/93.
for 415/93.
That expression is called the continued fraction representation of 415/93. This can be represented by the abbreviated notation 415/93 = [4; 2, 6, 7]. It is customary to place a semicolon after the first number to indicate that it is the whole part. Some older textbooks use all commas in the (n + 1)-tuple, for example, [4, 2, 6, 7].[2][3]
If the starting number is rational, then this process exactly parallels the Euclidean algorithm applied to the numerator and denominator of the number. In particular, it must terminate and produce a finite continued fraction representation of the number. The sequence of integers that occur in this representation is the sequence of successive quotients computed by the Euclidean algorithm. If the starting number is irrational, then the process continues indefinitely. This produces a sequence of approximations, all of which are rational numbers, and these converge to the starting number as a limit. This is the (infinite) continued fraction representation of the number. Examples of continued fraction representations of irrational numbers are:
√19 = [4;2,1,3,1,2,8,2,1,3,1,2,8,...] (sequence A010124 in the OEIS). The pattern repeats indefinitely with a period of 6. e = [2;1,2,1,1,4,1,1,6,1,1,8,...] (sequence A003417 in the OEIS). The pattern repeats indefinitely with a period of 3 except that 2 is added to one of the terms in each cycle. π = [3;7,15,1,292,1,1,1,2,1,3,1,...] (sequence A001203 in the OEIS). No pattern has ever been found in this representation. φ = [1;1,1,1,1,1,1,1,1,1,1,1,...] (sequence A000012 in the OEIS). The golden ratio, the irrational number that is the "most difficult" to approximate rationally (see § A property of the golden ratio φ below). γ = [0;1,1,2,1,2,1,4,3,13,5,1,...] (sequence A002852 in the OEIS). The Euler–Mascheroni constant, which is expected but not known to be irrational, and whose continued fraction has no apparent pattern.Continued fractions are, in some ways, more "mathematically natural" representations of a real number than other representations such as decimal representations, and they he several desirable properties:
The continued fraction representation for a real number is finite if and only if it is a rational number. In contrast, the decimal representation of a rational number may be finite, for example 137/1600 = 0.085625, or infinite with a repeating cycle, for example 4/27 = 0.148148148148... Every rational number has an essentially unique simple continued fraction representation. Each rational can be represented in exactly two ways, since [a0;a1,... an−1,an] = [a0;a1,... an−1,(an−1),1]. Usually the first, shorter one is chosen as the canonical representation. The simple continued fraction representation of an irrational number is unique. (However, additional representations are possible when using generalized continued fractions; see below.) The real numbers whose continued fraction eventually repeats are precisely the quadratic irrationals.[4] For example, the repeating continued fraction [1;1,1,1,...] is the golden ratio, and the repeating continued fraction [1;2,2,2,...] is the square root of 2. In contrast, the decimal representations of quadratic irrationals are apparently random. The square roots of all (positive) integers that are not perfect squares are quadratic irrationals, and hence are unique periodic continued fractions. The successive approximations generated in finding the continued fraction representation of a number, that is, by truncating the continued fraction representation, are in a certain sense (described below) the "best possible". Formulation[edit]A continued fraction in canonical form is an expression of the form
a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 1 ⋱ {\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\vphantom {\cfrac {1}{1}}}{_{\ddots }}}}}}}}}
where ai are integer numbers, called the coefficients or terms of the continued fraction.[1]
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.[5] When the terms eventually repeat from some point onwards, the continued fraction is called periodic.[4]
Thus, all of the following illustrate valid finite simple continued fractions:
Examples of finite simple continued fractions Formula Numeric Remarks a 0 {\displaystyle \ a_{0}} 2 {\displaystyle \ 2} All integers are a degenerate case a 0 + 1 a 1 {\displaystyle \ a_{0}+{\cfrac {1}{a_{1}}}} 2 + 1 3 {\displaystyle \ 2+{\cfrac {1}{3}}} Simplest possible fractional form a 0 + 1 a 1 + 1 a 2 {\displaystyle \ a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}}}}}} − 3 + 1 2 + 1 18 {\displaystyle \ -3+{\cfrac {1}{2+{\cfrac {1}{18}}}}} First integer may be negative a 0 + 1 a 1 + 1 a 2 + 1 a 3 {\displaystyle \ a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}}}}}}}} 1 15 + 1 1 + 1 102 {\displaystyle \ {\cfrac {1}{15+{\cfrac {1}{1+{\cfrac {1}{102}}}}}}} First integer may be zero
2
{\displaystyle \ 2}
All integers are a degenerate case
a
0
+
1
a
1
{\displaystyle \ a_{0}+{\cfrac {1}{a_{1}}}}
2
+
1
3
{\displaystyle \ 2+{\cfrac {1}{3}}}
Simplest possible fractional form
a
0
+
1
a
1
+
1
a
2
{\displaystyle \ a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}}}}}}
−
3
+
1
2
+
1
18
{\displaystyle \ -3+{\cfrac {1}{2+{\cfrac {1}{18}}}}}
First integer may be negative
a
0
+
1
a
1
+
1
a
2
+
1
a
3
{\displaystyle \ a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}}}}}}}}
1
15
+
1
1
+
1
102
{\displaystyle \ {\cfrac {1}{15+{\cfrac {1}{1+{\cfrac {1}{102}}}}}}}
First integer may be zero
For simple continued fractions of the form
r = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 1 ⋱ {\displaystyle r=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\vphantom {\cfrac {1}{1}}}{_{\ddots }}}}}}}}}
the a n {\displaystyle a_{n}} term can be calculated from the following recursive sequence:
term can be calculated from the following recursive sequence:
f n + 1 = 1 f n − ⌊ f n ⌋ {\displaystyle f_{n+1}={\frac {1}{f_{n}-\lfloor f_{n}\rfloor }}}
where f 0 = r {\displaystyle f_{0}=r} and a n = ⌊ f n ⌋ {\displaystyle a_{n}=\left\lfloor f_{n}\right\rfloor } .
and
a
n
=
⌊
f
n
⌋
{\displaystyle a_{n}=\left\lfloor f_{n}\right\rfloor }
.
from which it can be understood that the a n {\displaystyle a_{n}} sequence stops if f n = ⌊ f n ⌋ {\displaystyle f_{n}=\lfloor f_{n}\rfloor } is an integer.
Notations[edit]
is an integer.
Consider a continued fraction expressed as
x = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 a 4 {\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{a_{4}}}}}}}}}}
Because such a continued fraction expression may take a significant amount of vertical space, a number of methods he been tried to shrink it.
Gottfried Leibniz sometimes used the notation[6]
x = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 a 4 , {\displaystyle {\begin{aligned}x=a_{0}+{\dfrac {1}{a_{1}}}{{} \atop +}\\[28mu]\ \end{aligned}}\!{\begin{aligned}{\dfrac {1}{a_{2}}}{{} \atop +}\\[2mu]\ \end{aligned}}\!{\begin{aligned}{\dfrac {1}{a_{3}}}{{} \atop +}\end{aligned}}\!{\begin{aligned}\\[2mu]{\dfrac {1}{a_{4}}},\end{aligned}}}![{\displaystyle {\begin{aligned}x=a_{0}+{\dfrac {1}{a_{1}}}{{} \atop +}\\[28mu]\ \end{aligned}}\!{\begin{aligned}{\dfrac {1}{a_{2}}}{{} \atop +}\\[2mu]\ \end{aligned}}\!{\begin{aligned}{\dfrac {1}{a_{3}}}{{} \atop +}\end{aligned}}\!{\begin{aligned}\\[2mu]{\dfrac {1}{a_{4}}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/039511be0bd9a0d2ea131234d4b5f0e84ee13a2b)
and later the same idea was taken even further with the nested fraction bars drawn aligned, for example by Alfred Pringsheim as
x = a 0 + | 1 a 1 | + | 1 a 2 | + | 1 a 3 | + | 1 a 4 | , {\displaystyle 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 {}},}
or in more common related notations as[7]
x = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 a 4 {\displaystyle x=a_{0}+{1 \over a_{1}+}\,{1 \over a_{2}+}\,{1 \over a_{3}+}\,{1 \over a_{4}}}
or
x = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 a 4 . {\displaystyle x=a_{0}+{1 \over a_{1}}{{} \atop +}{1 \over a_{2}}{{} \atop +}{1 \over a_{3}}{{} \atop +}{1 \over a_{4}}.}
Carl Friedrich Gauss used a notation reminiscent of summation notation,
x = a 0 + K 4 i = 1 1 a i , {\displaystyle x=a_{0}+{\underset {i=1}{\overset {4}{\mathrm {K} }}}~{\frac {1}{a_{i}}},}
or in cases where the numerator is always 1, eliminated the fraction bars altogether, writing a list-style
x = [ a 0 ; a 1 , a 2 , a 3 , a 4 ] . {\displaystyle x=[a_{0};a_{1},a_{2},a_{3},a_{4}].}![{\displaystyle x=[a_{0};a_{1},a_{2},a_{3},a_{4}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a5812947e8c686698e0bb9b026f2586333d1c93)
Sometimes list-style notation uses angle brackets instead,
x = ⟨ a 0 ; a 1 , a 2 , a 3 , a 4 ⟩ . {\displaystyle x=\left\langle a_{0};a_{1},a_{2},a_{3},a_{4}\right\rangle .}
The semicolon in the square and angle bracket notations is sometimes replaced by a comma.[2][3]
One may also define infinite simple continued fractions as limits:
[ a 0 ; a 1 , a 2 , a 3 , … ] = lim n → ∞ [ a 0 ; a 1 , a 2 , … , a n ] . {\displaystyle [a_{0};a_{1},a_{2},a_{3},\,\ldots \,]=\lim _{n\to \infty }\,[a_{0};a_{1},a_{2},\,\ldots ,a_{n}].}![{\displaystyle [a_{0};a_{1},a_{2},a_{3},\,\ldots \,]=\lim _{n\to \infty }\,[a_{0};a_{1},a_{2},\,\ldots ,a_{n}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf80b82f0ab33bf81e98d6e776f3ed1689621cd8)
This limit exists for any choice of a 0 {\displaystyle a_{0}} and positive integers a 1 , a 2 , … {\displaystyle a_{1},a_{2},\ldots } .[8][9]
Calculating continued fraction representations[edit]
and positive integers
a
1
,
a
2
,
…
{\displaystyle a_{1},a_{2},\ldots }
.[8][9]
Consider a real number r {\displaystyle r} . Let i = ⌊ r ⌋ {\displaystyle i=\lfloor r\rfloor } and let f = r − i {\displaystyle f=r-i} . When f ≠ 0 {\displaystyle f\neq 0} , the continued fraction representation of r {\displaystyle r} is [ i ; a 1 , a 2 , … ] {\displaystyle [i;a_{1},a_{2},\ldots ]} , where [ a 1 ; a 2 , … ] {\displaystyle [a_{1};a_{2},\ldots ]} is the continued fraction representation of 1 / f {\displaystyle 1/f} . When r ≥ 0 {\displaystyle r\geq 0} , then i {\displaystyle i} is the integer part of r {\displaystyle r} , and f {\displaystyle f} is the fractional part of r {\displaystyle r} .
.
Let
i
=
⌊
r
⌋
{\displaystyle i=\lfloor r\rfloor }
and let
f
=
r
−
i
{\displaystyle f=r-i}
.
When
f
≠
0
{\displaystyle f\neq 0}
, the continued fraction representation of
r
{\displaystyle r}
![{\displaystyle [i;a_{1},a_{2},\ldots ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b07b4d8c246f2abcea1bd95ed28bdc2535c26d2d)
, where
[
a
1
;
a
2
,
…
]
{\displaystyle [a_{1};a_{2},\ldots ]}
![{\displaystyle [a_{1};a_{2},\ldots ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c9e8939f732f72d1740b63e3b794712d12cb2ff)
is the continued fraction representation of
1
/
f
{\displaystyle 1/f}
. When
r
≥
0
{\displaystyle r\geq 0}
, then
i
{\displaystyle i}
is the integer part of
r
{\displaystyle r}
is the fractional part of
r
{\displaystyle r}
In order to calculate a continued fraction representation of a number r {\displaystyle r} , write down the floor of r {\displaystyle r} . Subtract this value from r {\displaystyle r} . If the difference is 0, stop; otherwise find the reciprocal of the difference and repeat. The procedure will halt if and only if r {\displaystyle r} 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 3.245 = 649 / 200 {\displaystyle 3.245=649/200} :
Step RealNumber Integerpart Fractionalpart Simplified Reciprocalof f 1 r = 649 200 {\displaystyle r={\frac {649}{200}}} i = 3 {\displaystyle i=3} f = 649 200 − 3 {\displaystyle f={\frac {649}{200}}-3} = 49 200 {\displaystyle ={\frac {49}{200}}} 1 f = 200 49 {\displaystyle {\frac {1}{f}}={\frac {200}{49}}} 2 r = 200 49 {\displaystyle r={\frac {200}{49}}} i = 4 {\displaystyle i=4} f = 200 49 − 4 {\displaystyle f={\frac {200}{49}}-4} = 4 49 {\displaystyle ={\frac {4}{49}}} 1 f = 49 4 {\displaystyle {\frac {1}{f}}={\frac {49}{4}}} 3 r = 49 4 {\displaystyle r={\frac {49}{4}}} i = 12 {\displaystyle i=12} f = 49 4 − 12 {\displaystyle f={\frac {49}{4}}-12} = 1 4 {\displaystyle ={\frac {1}{4}}} 1 f = 4 1 {\displaystyle {\frac {1}{f}}={\frac {4}{1}}} 4 r = 4 {\displaystyle r=4} i = 4 {\displaystyle i=4} f = 4 − 4 {\displaystyle f=4-4} = 0 {\displaystyle =0} STOP
:
i
=
3
{\displaystyle i=3}
f
=
649
200
−
3
{\displaystyle f={\frac {649}{200}}-3}
=
49
200
{\displaystyle ={\frac {49}{200}}}
1
f
=
200
49
{\displaystyle {\frac {1}{f}}={\frac {200}{49}}}
2
r
=
200
49
{\displaystyle r={\frac {200}{49}}}
i
=
4
{\displaystyle i=4}
f
=
200
49
−
4
{\displaystyle f={\frac {200}{49}}-4}
=
4
49
{\displaystyle ={\frac {4}{49}}}
1
f
=
49
4
{\displaystyle {\frac {1}{f}}={\frac {49}{4}}}
3
r
=
49
4
{\displaystyle r={\frac {49}{4}}}
i
=
12
{\displaystyle i=12}
f
=
49
4
−
12
{\displaystyle f={\frac {49}{4}}-12}
=
1
4
{\displaystyle ={\frac {1}{4}}}
1
f
=
4
1
{\displaystyle {\frac {1}{f}}={\frac {4}{1}}}
4
r
=
4
{\displaystyle r=4}
i
=
4
{\displaystyle i=4}
=
0
{\displaystyle =0}
STOP
The continued fraction for 3.245 {\displaystyle 3.245} is thus [ 3 ; 4 , 12 , 4 ] , {\displaystyle [3;4,12,4],} or, expanded:
is thus
[
3
;
4
,
12
,
4
]
,
{\displaystyle [3;4,12,4],}
![{\displaystyle [3;4,12,4],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04b5353f052c6af0495a58d3942ffb1760c0c2d1)
or, expanded:
649 200 = 3 + 1 4 + 1 12 + 1 4 . {\displaystyle {\frac {649}{200}}=3+{\cfrac {1}{4+{\cfrac {1}{12+{\cfrac {1}{4}}}}}}.}
Finding graphically the continued fraction of a number by repeatedly fitting the largest possible square into an oblong of that aspect ratio
Reciprocals[edit]
The continued fraction representations of a positive rational number and its 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 [ a 0 ; a 1 , a 2 , … , a n ] {\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{n}]} and [ 0 ; a 0 , a 1 , … , a n ] {\displaystyle [0;a_{0},a_{1},\ldots ,a_{n}]} are reciprocals.
![{\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71653aa3956cbe5900ac604c537ea47bb3c0c663)
and
[
0
;
a
0
,
a
1
,
…
,
a
n
]
{\displaystyle [0;a_{0},a_{1},\ldots ,a_{n}]}
![{\displaystyle [0;a_{0},a_{1},\ldots ,a_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9720f5fea78d62b863755765438517dbce260f01)
are reciprocals.
For instance if a {\displaystyle a} is an integer and x 1 {\displaystyle x>1} then
x = a + 1 b {\displaystyle x=a+{\frac {1}{b}}} and 1 x = 0 + 1 a + 1 b {\displaystyle {\frac {1}{x}}=0+{\frac {1}{a+{\frac {1}{b}}}}} .
is an integer and
x
1
{\displaystyle x>1}
then
and
1
x
=
0
+
1
a
+
1
b
{\displaystyle {\frac {1}{x}}=0+{\frac {1}{a+{\frac {1}{b}}}}}
.
The last number that generates the remainder of the continued fraction is the same for both x {\displaystyle x} and its reciprocal.
and its reciprocal.
For example,
2.25 = 9 4 = [ 2 ; 4 ] {\displaystyle 2.25={\frac {9}{4}}=[2;4]} and 1 2.25 = 4 9 = [ 0 ; 2 , 4 ] {\displaystyle {\frac {1}{2.25}}={\frac {4}{9}}=[0;2,4]} . Finite continued fractions[edit]![{\displaystyle 2.25={\frac {9}{4}}=[2;4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/036681a2e2aeb96f756b8747415014be2408ffef)
and
1
2.25
=
4
9
=
[
0
;
2
,
4
]
{\displaystyle {\frac {1}{2.25}}={\frac {4}{9}}=[0;2,4]}
![{\displaystyle {\frac {1}{2.25}}={\frac {4}{9}}=[0;2,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6018b6136e762f15bb9a9344904c10e9aa56b822)
.
Finite continued fractions[edit]
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:
[a0; a1, a2, ..., an − 1, an, 1] = [a0; a1, a2, ..., an − 1, an + 1]. [a0; 1] = [a0 + 1]. Infinite continued fractions and convergents [edit]
Convergents approaching the golden ratio
Every infinite continued fraction is 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.[10][11] The larger a term is in the continued fraction, the closer the corresponding convergent is to the irrational number being approximated. Numbers like π he occasional large terms in their continued fraction, which makes them easy to approximate with rational numbers. Other numbers like e he 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 [a0; a1, a2, ...], the first four convergents (numbered 0 through 3) are
a 0 1 , a 1 a 0 + 1 a 1 , a 2 ( a 1 a 0 + 1 ) + a 0 a 2 a 1 + 1 , a 3 ( a 2 ( a 1 a 0 + 1 ) + a 0 ) + ( a 1 a 0 + 1 ) a 3 ( a 2 a 1 + 1 ) + a 1 . {\displaystyle {\frac {a_{0}}{1}},\,{\frac {a_{1}a_{0}+1}{a_{1}}},\,{\frac {a_{2}(a_{1}a_{0}+1)+a_{0}}{a_{2}a_{1}+1}},\,{\frac {a_{3}{\bigl (}a_{2}(a_{1}a_{0}+1)+a_{0}{\bigr )}+(a_{1}a_{0}+1)}{a_{3}(a_{2}a_{1}+1)+a_{1}}}.}
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 polynomials called continuants.
If successive convergents are found, with numerators h1, h2, ... and denominators k1, k2, ... then the relevant recursive relation is that of Gaussian brackets:
h n = a n h n − 1 + h n − 2 , k n = a n k n − 1 + k n − 2 . {\displaystyle {\begin{aligned}h_{n}&=a_{n}h_{n-1}+h_{n-2},\\[3mu]k_{n}&=a_{n}k_{n-1}+k_{n-2}.\end{aligned}}}![{\displaystyle {\begin{aligned}h_{n}&=a_{n}h_{n-1}+h_{n-2},\\[3mu]k_{n}&=a_{n}k_{n-1}+k_{n-2}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe1234bce11282297be9a8ce2becb80696e7b7f)
The successive convergents are given by the formula
h n k n = a n h n − 1 + h n − 2 a n k n − 1 + k n − 2 . {\displaystyle {\frac {h_{n}}{k_{n}}}={\frac {a_{n}h_{n-1}+h_{n-2}}{a_{n}k_{n-1}+k_{n-2}}}.}
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 0⁄1 and 1⁄0. For example, here are the convergents for [0;1,5,2,2].
n −2 −1 0 1 2 3 4 an 0 1 5 2 2 hn 0 1 0 1 5 11 27 kn 1 0 1 1 6 13 32When using the 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, ... , 2k−1, ... For example, the continued fraction expansion for 3 {\displaystyle {\sqrt {3}}} is [1; 1, 2, 1, 2, 1, 2, 1, 2, ...]. Comparing the convergents with the approximants derived from the Babylonian method:
n −2 −1 0 1 2 3 4 5 6 7 an 1 1 2 1 2 1 2 1 hn 0 1 1 2 5 7 19 26 71 97 kn 1 0 1 1 3 4 11 15 41 56 x0 = 1 = 1/1 x1 = 1/2(1 + 3/1) = 2/1 = 2 x2 = 1/2(2 + 3/2) = 7/4 x3 = 1/2(7/4 + 3/7/4) = 97/56 Properties[edit]
is [1; 1, 2, 1, 2, 1, 2, 1, 2, ...]. Comparing the convergents with the approximants derived from the Babylonian method:
The 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 usual topology on the reals). The infinite continued fraction also provides a map between the quadratic irrationals and the dyadic rationals, 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 transformations hing 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[edit]If a 0 , {\displaystyle \ a_{0}\ ,} a 1 , {\displaystyle a_{1}\ ,} a 2 , {\displaystyle a_{2}\ ,} … {\displaystyle \ \ldots \ } is an infinite sequence of positive integers, define the sequences h n {\displaystyle \ h_{n}\ } and k n {\displaystyle \ k_{n}\ } recursively:
h n = a n h n − 1 + h n − 2 , {\displaystyle h_{n}=a_{n}\ h_{n-1}+h_{n-2}\ ,} h − 1 = 1 , {\displaystyle h_{-1}=1\ ,} h − 2 = 0 ; {\displaystyle h_{-2}=0\ ;} k n = a n k n − 1 + k n − 2 , {\displaystyle k_{n}=a_{n}\ k_{n-1}+k_{n-2}\ ,} k − 1 = 0 , {\displaystyle k_{-1}=0\ ,} k − 2 = 1 . {\displaystyle k_{-2}=1~.}
a
1
,
{\displaystyle a_{1}\ ,}
a
2
,
{\displaystyle a_{2}\ ,}
…
{\displaystyle \ \ldots \ }
is an infinite sequence of positive integers, define the sequences
h
n
{\displaystyle \ h_{n}\ }
and
k
n
{\displaystyle \ k_{n}\ }
recursively:
h
−
1
=
1
,
{\displaystyle h_{-1}=1\ ,}
h
−
2
=
0
;
{\displaystyle h_{-2}=0\ ;}
k
n
=
a
n
k
n
−
1
+
k
n
−
2
,
{\displaystyle k_{n}=a_{n}\ k_{n-1}+k_{n-2}\ ,}
k
−
1
=
0
,
{\displaystyle k_{-1}=0\ ,}
k
−
2
=
1
.
{\displaystyle k_{-2}=1~.}
Theorem 1. For any positive real number x {\displaystyle \ x\ }
[ a 0 ; a 1 , … , a n − 1 , x ] = x h n − 1 + h n − 2 x k n − 1 + k n − 2 , [ a 0 ; a 1 , … , a n − 1 + x ] = h n − 1 + x h n − 2 k n − 1 + x k n − 2 {\displaystyle \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}+xk_{n-2}\ }}}
![{\displaystyle \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}+xk_{n-2}\ }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e97a1dad360f5a7faaacd6f7e99ec9fd53ba6125)
Theorem 2. The convergents of [ a 0 ; {\displaystyle \ [\ a_{0}\ ;} a 1 , {\displaystyle a_{1}\ ,} a 2 , {\displaystyle a_{2}\ ,} … ] {\displaystyle \ldots \ ]\ } are given by
[ a 0 ; a 1 , … , a n ] = h n k n . {\displaystyle \left[\ a_{0};\ a_{1},\ \dots ,a_{n}\ \right]={\frac {h_{n}}{\ k_{n}\ }}~.}
a
1
,
{\displaystyle a_{1}\ ,}
![{\displaystyle \ldots \ ]\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f28bcc28d8f19cfd10ba8688e2dabc22dd3c7bcc)
are given by
![{\displaystyle \left[\ a_{0};\ a_{1},\ \dots ,a_{n}\ \right]={\frac {h_{n}}{\ k_{n}\ }}~.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad872265234f8206c1a1b92676f2d01699ee1e3b)
or in matrix form, [ h n h n − 1 k n k n − 1 ] = [ a 0 1 1 0 ] ⋯ [ a n 1 1 0 ] {\displaystyle {\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}}}
Theorem 3. If the n {\displaystyle \ n} th convergent to a continued fraction is h n k n , {\displaystyle \ {\frac {h_{n}}{k_{n}}}\ ,} then
k n h n − 1 − k n − 1 h n = ( − 1 ) n , {\displaystyle k_{n}\ h_{n-1}-k_{n-1}\ h_{n}=(-1)^{n}\ ,}
th convergent to a continued fraction is
h
n
k
n
,
{\displaystyle \ {\frac {h_{n}}{k_{n}}}\ ,}
then
or equivalently
h n k n − h n − 1 k n − 1 = ( − 1 ) n + 1 k n − 1 k n . {\displaystyle {\frac {h_{n}}{\ k_{n}\ }}-{\frac {h_{n-1}}{\ k_{n-1}\ }}={\frac {(-1)^{n+1}}{\ k_{n-1}\ k_{n}\ }}~.}
Corollary 1: Each convergent is in its lowest terms (for if h n {\displaystyle \ h_{n}\ } and k n {\displaystyle \ k_{n}\ } had a nontrivial common divisor it would divide k n h n − 1 − k n − 1 h n , {\displaystyle \ k_{n}\ h_{n-1}-k_{n-1}\ h_{n}\ ,} which is impossible).
which is impossible).
Corollary 2: The difference between successive convergents is a fraction whose numerator is unity:
h n k n − h n − 1 k n − 1 = h n k n − 1 − k n h n − 1 k n k n − 1 = ( − 1 ) n + 1 k n k n − 1 . {\displaystyle {\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}\ }}~.}
Corollary 3: The continued fraction is equivalent to a series of alternating terms:
a 0 + ∑ n = 0 ∞ ( − 1 ) n k n k n + 1 . {\displaystyle a_{0}+\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{\ k_{n}\ k_{n+1}\ }}~.}
Corollary 4: The matrix
[ h n h n − 1 k n k n − 1 ] = [ a 0 1 1 0 ] ⋯ [ a n 1 1 0 ] {\displaystyle {\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}}}has determinant ( − 1 ) n + 1 {\displaystyle (-1)^{n+1}} , and thus belongs to the group of 2 × 2 {\displaystyle \ 2\times 2\ } unimodular matrices G L ( 2 , Z ) . {\displaystyle \ \mathrm {GL} (2,\mathbb {Z} )~.}
, and thus belongs to the group of
2
×
2
{\displaystyle \ 2\times 2\ }
unimodular matrices
G
L
(
2
,
Z
)
.
{\displaystyle \ \mathrm {GL} (2,\mathbb {Z} )~.}
Corollary 5: The matrix [ h n h n − 2 k n k n − 2 ] = [ h n − 1 h n − 2 k n − 1 k n − 2 ] [ a n 0 1 1 ] {\displaystyle {\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}}} has determinant ( − 1 ) n a n {\displaystyle (-1)^{n}a_{n}} , or equivalently, h n k n − h n − 2 k n − 2 = ( − 1 ) n k n − 2 k n a n {\displaystyle {\frac {h_{n}}{\ k_{n}\ }}-{\frac {h_{n-2}}{\ k_{n-2}\ }}={\frac {(-1)^{n}}{\ k_{n-2}\ k_{n}\ }}a_{n}} meaning that the odd terms monotonically decrease, while the even terms monotonically increase.
has determinant
(
−
1
)
n
a
n
{\displaystyle (-1)^{n}a_{n}}
, or equivalently,
h
n
k
n
−
h
n
−
2
k
n
−
2
=
(
−
1
)
n
k
n
−
2
k
n
a
n
{\displaystyle {\frac {h_{n}}{\ k_{n}\ }}-{\frac {h_{n-2}}{\ k_{n-2}\ }}={\frac {(-1)^{n}}{\ k_{n-2}\ k_{n}\ }}a_{n}}
meaning that the odd terms monotonically decrease, while the even terms monotonically increase.
Corollary 6: The denominator sequence k 0 , k 1 , k 2 , … {\displaystyle k_{0},k_{1},k_{2},\dots } satisfies the recurrence relation k − 1 = 0 , k 0 = 1 , k n = k n − 1 a n + k n − 2 {\displaystyle k_{-1}=0,k_{0}=1,k_{n}=k_{n-1}a_{n}+k_{n-2}} , and grows at least as fast as the Fibonacci sequence, which itself grows like O ( ϕ n ) {\displaystyle O(\phi ^{n})} where ϕ = 1.618 … {\displaystyle \phi =1.618\dots } is the golden ratio.
satisfies the recurrence relation
k
−
1
=
0
,
k
0
=
1
,
k
n
=
k
n
−
1
a
n
+
k
n
−
2
{\displaystyle k_{-1}=0,k_{0}=1,k_{n}=k_{n-1}a_{n}+k_{n-2}}
, and grows at least as fast as the Fibonacci sequence, which itself grows like
O
(
ϕ
n
)
{\displaystyle O(\phi ^{n})}
where
ϕ
=
1.618
…
{\displaystyle \phi =1.618\dots }
is the golden ratio.
Theorem 4. Each ( s {\displaystyle \ s} th) convergent is nearer to a subsequent ( n {\displaystyle \ n} th) convergent than any preceding ( r {\displaystyle \ r} th) convergent is. In symbols, if the n {\displaystyle \ n} th convergent is taken to be [ a 0 ; a 1 , … , a n ] = x n , {\displaystyle \ \left[\ a_{0};\ a_{1},\ \ldots ,\ a_{n}\ \right]=x_{n}\ ,} then
| x r − x n | > | x s − x n | {\displaystyle \left|\ x_{r}-x_{n}\ \right|>\left|\ x_{s}-x_{n}\ \right|}
th) convergent is nearer to a subsequent (
n
{\displaystyle \ n}
th) convergent is. In symbols, if the
n
{\displaystyle \ n}
![{\displaystyle \ \left[\ a_{0};\ a_{1},\ \ldots ,\ a_{n}\ \right]=x_{n}\ ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21fa0305affc343d457f54edf63f48b4e63aaa91)
then
for all r