Simple continued fraction

A simple or regular continued fraction is a continued fraction with numerators all equal to one, and denominators built from a sequence of integer numbers. The sequence can be finite or infinite, resulting in a finite continued fraction like
or an infinite continued fraction like
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 are called the coefficients or terms of the continued fraction.
Simple continued fractions have a number of remarkable properties related to the Euclidean algorithm for integers or real numbers. Every rational number has two closely related expressions as a finite continued fraction, whose coefficients can be determined by applying the Euclidean algorithm to. 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 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 and 1. This way of expressing real numbers is called their continued fraction representation.

Motivation and notation

Consider, for example, the rational number, which is around 4.4624. As a first approximation, start with 4, which is the integer part;. The fractional part is the reciprocal of which is about 2.1628. Use the integer part, 2, as an approximation for the reciprocal to obtain a second approximation of ;
the remaining fractional part,, is the reciprocal of, and is around 6.1429. Use 6 as an approximation for this to obtain as an approximation for and, about 4.4615, as the third approximation. Further,. Finally, the fractional part,, is the reciprocal of 7, so its approximation in this scheme, 7, is exact and produces the exact expression for.
That expression is called the continued fraction representation of. This can be represented by the abbreviated notation = . 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 -tuple, for example, .
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 continued fraction representation of the number. Examples of continued fraction representations of irrational numbers are:

. The pattern repeats indefinitely with a period of 6.
. The pattern repeats indefinitely with a period of 3 except that 2 is added to one of the terms in each cycle.
. No pattern has ever been found in this representation.
. The golden ratio, the irrational number that is the "most difficult" to approximate rationally.
. 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 have 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, or infinite with a repeating cycle, for example
Every rational number has an essentially unique simple continued fraction representation. Each rational can be represented in exactly two ways, since. Usually the first, shorter one is chosen as the canonical representation.
The simple continued fraction representation of an irrational number is unique.
The real numbers whose continued fraction eventually repeats are precisely the quadratic irrationals. For example, the repeating continued fraction is the golden ratio, and the repeating continued fraction is the square root of 2. In contrast, the decimal representations of quadratic irrationals are apparently random. The square roots of all 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 the "best possible".
Formulation

A continued fraction in canonical form is an expression of the form
where a_i are integer numbers, called the coefficients or terms of the continued fraction.
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.
When the terms eventually repeat from some point onwards, the continued fraction is called periodic.
Thus, all of the following illustrate valid finite simple continued fractions:

Formula	Numeric	Remarks
		All integers are a degenerate case
		Simplest possible fractional form
		First integer may be negative
		First integer may be zero

For simple continued fractions of the form
the term can be calculated from the following recursive sequence:
where and.
from which it can be understood that the sequence stops if is an integer.

Notations

Consider a continued fraction expressed as
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 Leibniz sometimes used the notation
and later the same idea was taken even further with the nested fraction bars drawn aligned, for example by Alfred Pringsheim as
or in more common related notations as
or
Carl Friedrich Gauss used a notation reminiscent of summation notation,
or in cases where the numerator is always 1, eliminated the fraction bars altogether, writing a list-style
Sometimes list-style notation uses angle brackets instead,
The semicolon in the square and angle bracket notations is sometimes replaced by a comma.
One may also define infinite simple continued fractions as limits:
This limit exists for any choice of and positive integers.

Calculating continued fraction representations

Consider a real number.
Let and let.
When, the continued fraction representation of is
, where is the continued fraction representation of. When, then is the integer part of, and is the fractional part of.
In order to calculate a continued fraction representation of a number, write down the floor of. Subtract this value from. If the difference is 0, stop; otherwise find the reciprocal of the difference and repeat. The procedure will halt if and only if 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 :
The continued fraction for is thus or, expanded:

Reciprocals

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
and are reciprocals.
For instance if is an integer and then
If then
The last number that generates the remainder of the continued fraction is the same for both and its reciprocal.
For example,

Finite continued fractions

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:

Infinite continued fractions and convergents

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. 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, the first four convergents are
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,,... and denominators,,... then the relevant recursive relation is that of Gaussian brackets:
The successive convergents are given by the formula
Thus to incorporate a new term into a rational approximation, only the two previous convergents are necessary. The initial "convergents" are ⁰⁄₁ and ¹⁄₀. For example, here are the convergents for .
When 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, ... , ,... For example, the continued fraction expansion for square root of 3| is. Comparing the convergents with the approximants derived from the Babylonian method: