Continued fraction

In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on.^[1] In a finite continued fraction (or terminated continued fraction), the iteration/recursion is terminated 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}$ are called the coefficients or terms of the continued fraction.^[2]

"Recurring fraction" redirects here. Not to be confused with Repeating decimal.

It is generally assumed that the numerator of all of the fractions is 1. If arbitrary values or functions are used in place of one or more of the numerators or the integers in the denominators, the resulting expression is a generalized continued fraction. When it is necessary to distinguish the first form from generalized continued fractions, the former may be called a simple or regular continued fraction, or said to be in canonical form.

Continued fractions have a number of remarkable properties related to the Euclidean algorithm for integers or real numbers. Every rational number $p$ / $q$ has two closely related expressions as a finite continued fraction, whose coefficients $a i$ can be determined by applying the Euclidean algorithm to $(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 $\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 $\alpha$ and 1. This way of expressing real numbers (rational and irrational) is called their continued fraction representation.

The term continued fraction may also refer to representations of rational functions, arising in their analytic theory. For this use of the term, see Padé approximation and Chebyshev rational functions.

$\sqrt 19 = [4;2,1,3,1,2,8,2,1,3,1,2,8,...]$ (sequence in the OEIS). The pattern repeats indefinitely with a period of 6.

A010124

$= [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.

e

$= [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.

γ

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 for 415/93.

The expression 4 + 1/2 + 1/6 + 1/7 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 replace only the first comma by a semicolon to indicate that the preceding number is the whole part.) Some older textbooks use all commas in the $(n + 1)$ -tuple, for example, [4, 2, 6, 7].^[3]^[4]

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:

Continued fractions are, in some ways, more "mathematically natural" representations of a real number than other representations such as decimal representations, and they have several desirable properties:

Comparison[edit]

Consider $x = [a 0; a 1, ...]$ and $y = [b 0; b 1, ...]$ . If $k$ is the smallest index for which $a k$ is unequal to $b k$ then $x < y$ if $(-1) k (a k - b k) < 0$ and $y < x$ otherwise.

If there is no such $k$ , but one expansion is shorter than the other, say $x = [a 0; a 1, ..., a n]$ and $y = [b 0; b 1, ..., b n, b n + 1, ...]$ with $a i = b i$ for $0 \leq i \leq n$ , then $x < y$ if $n$ is even and $y < x$ if $n$ is odd.

Applications[edit]

Square roots[edit]

Generalized continued fractions are used in a method for computing square roots.

The identity

300 BCE contains an algorithm for the greatest common divisor, whose modern version generates a continued fraction as the sequence of quotients of successive Euclidean divisions that occur in it.

Euclid's Elements

499 The contains the solution of indeterminate equations using continued fractions

Aryabhatiya

1572 , L'Algebra Opera – method for the extraction of square roots which is related to continued fractions

Rafael Bombelli

1613 , Trattato del modo brevissimo di trovar la radice quadra delli numeri – first notation for continued fractions

Pietro Cataldi

Gaussian brackets

– generalization of continued fractions in which the partial numerators and partial denominators can assume arbitrary complex values

Generalized continued fraction

Periodic continued fraction

Continued Logarithms

Complete quotient

– Algorithms for calculating square roots

Computing continued fractions of square roots

– Finite sum of distinct unit fractions

Egyptian fraction

– decomposition of a positive real number into a series of unit fractions, each an integer multiple of the next one

Engel expansion

– Connects a very general infinite series with an infinite continued fraction.

Euler's continued fraction formula

– Mathematical theory about infinitely iterated function composition

Infinite compositions of analytic functions

– Mathematical concept

Infinite product

– Repeated application of an operation to a sequence

Iterated binary operation

– Concept in the geometry of numbers

Klein polyhedron

Mathematical constants by continued fraction representation

Restricted partial quotients

– Ordered binary tree of rational numbers

Stern–Brocot tree

– Criterion for convergence of continued fractions

Śleszyński–Pringsheim theorem

Afifi, Haitham; Auroux, Sébastien; Karl, Holger (April 2018). "MARVELO: Wireless virtual network embedding for overlay graphs with loops". 2018 IEEE Wireless Communications and Networking Conference (WCNC). IEEE. pp. 1–6. :1712.06676. doi:10.1109/WCNC.2018.8377194. ISBN 978-1-5386-1734-2. S2CID 13447977.

arXiv

, Encyclopedia of Mathematics, EMS Press, 2001 [1994]

"Continued fraction"

Knott, Ron (2018). . Retrieved 26 April 2022.