Continued fraction

In mathematics, a continued fraction, also called a continued fraction (influenced by the English continued fraction), is an expression Shape:

${displaystyle x=a_{0}+{cfrac {1}{a_{1} +{cfrac {1}{a_{2}+{cfrac {1}{a_{3}}}{cfrac {1}{ddots }}}}}}}}}$

where a₀ is an integer and all other numbers are a_i are positive integers, for i= 0, 1, 2,...n,.... The numbers a₀, a₁, a ₂,..., a_s are called elements or incomplete quotients. If the numerators or partial denominators are allowed to take on arbitrary values, which might be functions in some context, the resulting expression is a generalized continued fraction. When it is necessary to distinguish the typical form above from a generalized one, it will be called regular continued fraction or simple.

Motivation

The study of continued fractions is motivated by the desire to give a "mathematically pure" representation of the real numbers. We are familiar with the decimal representation:

${displaystyle r=sum _{i=0}^{infty }a$

where a₀ can be any integer and the others a_i belong to {0, 1, 2,..., 9}. So the number ${displaystyle pi }$for example, it is represented with succession (3, 1, 4, 1, 5, 9, 2,...).

This representation has some problems. For example, the constant 10 is used because the calculations are done in the decimal system; either octal or binary could be used. Another problem is that many rationals do not have a finite representation; for example, 1/3 does it with the infinite sequence (0, 3, 3, …).

The continued fraction representation of real numbers avoids both problems. For example, let's consider the number 415/93, which is worth approximately 4.4624. This is about 4, but it's somewhat greater than 4, about 4+1/2. But the denominator 2 is not correct; a slightly larger one would be, about 2+1/6, since 415/93 is roughly 4+1/(2+1/6). But the denominator 6 is not correct; it would be a slightly larger one, about 4+1/(2+1/(6+1/7)). This is exact. Removing the redundant parts of the expression 4+1/(2+1/(6+1/7)), we get its shorthand notation [4; 2, 6, 7].

Thus, any real number can be represented as a continued fraction, and these comfortable properties are fulfilled:

• The representation in continuous fraction of a real number is finite if and only if that number is rational.
• The representation in continuous fraction of a rational “simple” is generally short.
• The representation in continuous fraction of a rational is unique whenever it does not end in 1. (in fact: [a₀; a₁... a_n, 1] = [a₀; a₁... a_n+ 1].)
• The terms of a continuous fraction will be repeated if and only if it represents a quadratic irrational, that is, if it is a solution of a quadratic equation with integer coefficients. For example, the continuous fraction [1; 1, 1,...] represents the golden number and [1; 2, 2, 2,...] to ${displaystyle {sqrt {2}}}$.
• The truncated representation in continuous fraction of a number x gives a rational approximation that is, in a sense, the "best possible" (see theorems 6 and 7, below, for a formalization of this assertion).

The last property, false if we use the conventional representation, is very important. If we truncate a decimal representation, we get a rational approximation, but usually not the best. For example, truncating 1/7=0.142857… in several places we will obtain approximations like 142/1000, 14/100 or 1/10. But it is clear that the best rational that approximates 1/7 is 1/7 itself. If we truncate the decimal representation of π we will obtain approximations like 31415/10000 or 314/100. The continued fraction representation of π begins with [3; 7, 15, 1, 292,...]. If we truncate this representation we will obtain the excellent approximations: 3, 22/7, 333/106, 355/113, 103993/33102, … The denominators of 314/100 and 333/106 are almost the same but the error in the approximation of 314/ 100 is nine times greater than that of 333/106, as well as the approximation to π with [3; 7, 15, 1] is 100 times more accurate than 3.1416.

Historical notes

Continuous fractions are used from ancient times. Aryabhata (476-550) it used them to solve diophantic equations, as well as to give precise approximations of irrational numbers. Brahmagupta (598-668) deepened in the study of the equations called Pell today. It developed the foundations of the chakravala method, using calculations similar to those of the continuous fractions. He investigated the resolution of the equation ${displaystyle x^{2}-61y^{2}=1}$finding the least solution: x = 1 766 319 049, and = 226 153 980

In the 12th century, the method was improved by Bhaskara II. An algorithm, analogous to that of continued fractions, made it possible to solve a general case. The most noticeable difference was that it allowed negative numbers in the fraction, speeding up convergence.

The appearance in Europe was later and Italian. Rafael Bombelli (1526-1572) used a forerunner of continued fractions to calculate approximations to the square root of 13. Pietro Antonio Cataldi (1548-1626) realized that Bombelli's method was valid for all square roots; he used it for the 18th and wrote a booklet on this subject. He remarked that the approximations obtained are alternately superior and inferior to the sought square root.

In England there was decisive progress. On January 3, 1657, Pierre de Fermat challenged European mathematicians with various problems, among which was the equation already resolved by Brahmagupta. The English response was quick. William Brouncker (1620-1684) found the relationship between the equation and the continuous fraction, as well as a algorithmic method equivalent to that of the Hindus for the calculation of the solution. It used a continuous fraction to build a succession that converged ${displaystyle 4/pi }$, and approached ${displaystyle pi }$ with 10 significant decimals. These results were published by John Wallis, who used to demonstrate the recurring relationships used by Brouncker and Baskara II. Dio, also, the name of continuous fraction in the sentence: «Nempe si unitati adjungatur fractio, quae denominatorem habeat continue fractum». At this time, Christiaan Huygens (1629-1695) He discovered that continuous fractions are the ideal tool to determine the number of teeth that must have the gear wheels of a watch. He used them for the construction of a planetary automaton.

In the next century some theoretical issues are resolved. The use showed that the algorithm of the continuous fractions allowed to resolve the Pell equation using the fact that the fraction is periodic from a point. Leonhard Euler (1707-1783) showed that if a number has a regular continuous fraction, then it is a solution of a second-degree equation with integer coefficients. The most subtle reciprocal is the work of Joseph-Louis de Lagrange (1736-1813) . Johann Heinrich Lambert (1728-1777) found a new usefulness of the continuous fractions: it used them to demonstrate the irrationality of ${displaystyle pi }$.

This use became frequent during the century XIX. Évariste Galois found a necessary and sufficient condition for a continuous fraction to be immediately periodic. Joseph Liouville (1809-1882) used the development in a generalized continuous fraction to build the first examples of transcendent numbers: the numbers of Liouville. Charles Hermite (1822-1901) established new methods to demonstrate the significance of ${displaystyle e}$base of the neperian logarithm. These are retaken by Ferdinand von Lindemann who demonstrated in 1882 that ${displaystyle pi }$ is transcendent with the corollary of the impossibility of the square of the circle. Georg Cantor (1845-1918) showed that the points of a segment can be put in bijection with those of the interior of a square with the help of continuous fractions. The century XX. saw the explosion of a large number of publications on this issue. More than 1500 mathematicians have found elements worthy of publication.

Calculating a continued fraction

Let us consider a real number r. Let e be the integer part and d the decimal part of r; then the continued fraction representation of r is [e; a₁, a₂,...], where [a< sub>1; a₂,...] is the continued fraction representation of 1/d.

To compute the continued fraction representation of a number r, write the integer part of r first. Subtract this integer part from r. If the difference is 0 it stops; otherwise, find the inverse of the difference and repeat. This process will end if and only if r is rational.

Find the continuous fraction of 3,245 (= ${displaystyle scriptstyle {3+,{49 over 200}}}}$)
Step	Actual number	Whole part	Fractionary part	Simplified	Reciprocal f	Simplified
1	r = ${displaystyle scriptstyle {3+,{49 over 200}}}}$	i = 3	f = ${displaystyle scriptstyle {3+,{49 over 200}}}}$ − 3	= ${displaystyle scriptstyle {49 over 200}}$	1/f = ${displaystyle scriptstyle {200 over 49}}$	= ${displaystyle scriptstyle {4+,{4 over 49}}}$
2	r = ${displaystyle scriptstyle {4+,{4 over 49}}}$	i = 4	f = ${displaystyle scriptstyle {4+,{4 over 49}}}$ − 4	= ${displaystyle scriptstyle {4 over 49}}$	1/f = ${displaystyle scriptstyle {49 over 4}}$	= ${displaystyle scriptstyle {12+,{1 over 4}}}}$
3	r = ${displaystyle scriptstyle {12+,{1 over 4}}}}$	i = 12	f = ${displaystyle scriptstyle {12+,{1 over 4}}}}$ − 12	= ${displaystyle scriptstyle {1 over 4}}$	1/f = ${displaystyle scriptstyle {4 over 1}}$	= 4
4	r = 4	i = 4	f = 4 - 4	= 0	THE END
The continuous fraction of 3.245 =(${displaystyle scriptstyle {3+,{49 over 200}}}}$) is [3; 4, 12, 4].
${displaystyle 3,245= left(3+,{49 over 200}right)=3+{cfrac {1}{4+{cfrac {1}{12+{cfrac {1}{1}{4}}}}}}}}}}$

It could also be represented by [3; 4, 12, 3, 1] in reference to finite continued fractions.

Notation

A continued fraction can be expressed as

${displaystyle x=[a_{0};a_{1},a_{2},a_{3}]};$

or, in Pringsheim notation,

${displaystyle x=a_{0}+{frac {1mid }{mid a_{1}}}}}}}{mid a_{2}}}}}{frac {1mid }{mid }{mid a_{3}}}}}}}$

or this other notation similar to the one above

${displaystyle x=a_{0}+{1 over a_{1}+}{1 over a_{2}}+}{1 over a_{3}+}}}$

You can define infinite continued fractions as a limit:

${displaystyle [a_{0};a_{1},a_{2},a_{3},,ldots ]=lim _{nto infty }[a_{0};a_{1},a_{2},ldotsa_{n}}}}}}}$

This limit exists for any choice of positive integers a₁, a₂, a ₃...

Formalization

We will call any expression of the form continued fraction of order n:

${displaystyle x=a_{0}+{cfrac {1}{a_{1}}{a_{2}+{cfrac {1}{begin{array}{l}{l}{l}{ddots \{a_{n-2}}{cfrac {1}{a_{n-1}{n}}}{n}}}{n}}}{a$

where ${displaystyle a_{0},}$ is a real non-negative and others are strictly positive. We will also use the notation: ${displaystyle [a_{0};a_{1},a_{2},a_{3},ldotsa_{n}}}}}$

Reduced

Sea ${displaystyle [a_{0};a_{1},a_{2},a_{3},ldotsa_{n}}}}}$ a continuous fraction: we define the succession p_k/q_k by:

${displaystyle {begin{cases}p_{0}=a_{0}q_{0}=1end{cases}}qquad {begin{cases}p_{1}=a_{0}a_{1}a_{1}{1}{1}=a_{1}{1}{1}}}}{1}}}{1}}}}}}}}$

and recurrence, for k ≥ 2

${displaystyle {begin{cases}p_{k}=a_{k}p_{k-1+}p_{k-2q_{k}=a_{k}q_{k-1}+q_{k-2}end{cases}}}}}$

The fraction p_k/q_k is called the th reduced k of the continued fraction.

From now on we will consider whole continued fractions, that is, those for which all a_i is a positive integer.

Let x be a positive real number, we can put it as a₀+x₀, where a₀ =[x] is the integer part of x y; x₀ <1 the decimal part of x.

Yeah. ${displaystyle x_{0}neq 0}$ So, in the same way, ${displaystyle {frac {1}{x_{0}}}}=a_{1}+x_{1}}}}}$, so that

${displaystyle x=a_{0}+{frac {1}{a_{1} +x_{1}}}}}}}}$.

Yeah. ${displaystyle x_{1}neq 0}$We'd put ${displaystyle {frac {1}{x_{1}}}}=a_{2}+x_{2}}}}$etc. We have then for kg1, ${displaystyle a_{k}={frac {1}{x_{k-1}}}}}-x_{k}}}}$ and ${displaystyle x_{k}={frac {1}{x_{k-1}}}}-a_{k}}}$ (always ${displaystyle x_{k-1}neq 0}$). We have:

${displaystyle x=[a_{0};a_{1},a_{2},dotsa_{k}+x_{k}}}}}$.

The sequence (a_k) is determined by x and is called Continued Fraction Expansion of x.

We can thus give a meaning to an infinite integer continued fraction and write:

${displaystyle x=[a_{0};a_{1},dotsa_{k},dots}$

where ${displaystyle x=lim _{k}p_{k}/q_{k}}}$.

Best Rational Approximations

Theorem 6. The reduced kth p_k / q_k of the continued fraction expansion of x is the best approximation of x by a fraction of denominator less than or equal to q_k :

${displaystyle leftΔx-{frac {p}{q}}}}{right entails `leftąx-{frac {p_{k}}{q_{k}}}}}}}right.$.

Theorem 7. Let x be a nonzero positive real number and p/q an irreducible fraction such that:

${displaystyle leftIVAx-{frac {p}{q}}}}{right implied{frac {1}{2q^{2}}}}}}$

Then, p/q is one of the reductions of the expansion of x in continued fraction.

Theorem 8. (Hurwitz) Let x be a positive irrational. There is an infinite number of rationals such that:

${displaystyle leftΔx-{frac {p}{q}}}}{{{{frac {1}{{{sqrt {5}}}q^{2}}}}}}}}}}}}}$.

In addition, the constant ${displaystyle {sqrt {5}}}$ It's the best possible.

In this last sense the golden number, ${displaystyle phi }$, is one of the worst irrationals approaching with continuous fractions; its reduced (5/3, 8/5, 13/8, 21/13, etc.), distan almost exactly ${displaystyle {frac {1}{{sqrt {5}}n^{2}}$ of ${displaystyle phi }$.

Some notable developments

Number π {displaystyle pi }

${displaystyle pi }$ = [3; 7, 15, 1, 292, 1,...] or either

${displaystyle pi =3+{cfrac {1}{7+{cfrac {1}{15+{cfrac {1}{1+{cfrac {1}{292+{cfrac {1}{1}{1+{cfrac} {1}{1}{1}{1+{cfrac} {1}{1}{1}{1}{1}{1}{1}{cf}}}}}}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{cf}}{1}{1}{1}{1}{1}{1}{1}}{1}{1st}{1}{cf}}}{1}}{1}}}{1}{1st}}}}{1st}{1st}{1st}{1st}}}}{$

Using generalized continued fractions we obtain expansions with more regular structures

${displaystyle pi ={cfrac {4}{1+{cfrac {1}{3+{cfrac {4}{5+{cfrac {9}{7+{cfrac {16}{9}{9+{cfrac {25}{11+{cfrac {36}{13+{cfrac {49}}{ddots}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}{1}}}}}}}}}}$

${displaystyle pi =3+{cfrac {1}{6+{cfrac {9}{6+{cfrac {25}{6+{cfrac {49}{6+{cfrac {81}{6+{cfrac {121}{ddots ,}}}}}}}}}$

Square root of 2

Sea square root of two: r=${displaystyle {sqrt {2}}}$Your whole part is worth 1, so ${displaystyle a_{0}=1}$ and ${displaystyle x_{0}=1/({sqrt {2}}-1)}$. Now, using the identity ${displaystyle ({sqrt {2}}-1)({sqrt {2}}+1}=1}$We have to ${displaystyle x_{0}={sqrt {2}}+1}$. So... ${displaystyle a_{1}=2}$ and ${displaystyle x_{1}={sqrt {2}}+1}$. We concluded that all ${displaystyle a_{k}=2}$ from k=1 are worth 2 and all ${displaystyle x_{k}}$ Okay. ${displaystyle {sqrt {2}}+1}$. Development in continuous fraction is therefore:

${displaystyle {sqrt {2}}=[1;2,2,2,dots]. !$

Golden Ratio

${displaystyle phi =[1;1,1,1,dots]. !$

Number e

${displaystyle e=[2;1,2,1,1,4,1,6,1,1,1,1,1,10,1,1.12,dots]. !$

Applications

Irrationality of number and {displaystyle e}

Continuous fractions offer a way of knowing the irrationality of a number. If your development is infinite then the number is irrational. This technique was used by Euler, which determined the continuous fraction of the number ${displaystyle e}$.

The continued fraction development of e, is:

${displaystyle {text{e}}=[2;overbrace {1,2,1}overbrace {1,4,1}cdotsoverbrace {1,2p,1}cdots ,]=[2,{overline {1,2p,1}}}]quad pin mathbb {N} -{{0}}}}$

The slash used here is a common notation; indicates an infinite repetition of the sequence of integers that it covers.

Or these others:

${displaystyle {sqrt {text{e}}}=[1,1,}{overline {1,4p+1,}1}}},quad tanh left({frac}{1}{2}{2}}{right}{frac}{1}{1⁄2}{1⁄2}}{1⁄2}}}{1⁄2}}}{1⁄2}}}}}}}{1⁄2}}}{1⁄2}}}}}}{1⁄2}}}}{1⁄2}}}}{1⁄2}}}}}}{1⁄2}}}}{$

It is concluded that neither e nor √e are rational.

Irrationality of number π {displaystyle pi }

The irrationality of the number ${displaystyle pi }$ It was first demonstrated by Johann Heinrich Lambert in 1761 on the basis of the ongoing widespread development of the tangent function.

Pell's Equation

Pell's equation is a Diophantine equation, that is, with integer coefficients and for which the requested solutions are also integers. It has the form:

${displaystyle x^{2}-ny^{2}=a;}$

Where n is an integer that is not perfect square and a It's not an integer. Here we will consider that ${displaystyle a=pm 1}$. A solution (h, k) verify: ${displaystyle (h-{sqrt {n}}cdot k)(h+{sqrt {n}}}cdot k)=pm 1quad {text{o}}}quad h-{sqrt {n}}{cdot k={frac {pm1}{h+{sqrt {n}{n}}{n}}{cdot$

h/k √n are greater than 1 and √n is strictly so, hence:

${displaystyle left ultimate{frac {h}{k}}-{sqrt {n}}{right}{frac {1}{({frac {h}{k}}}}}{sqrt {n}}})cdot k^{2}}}{frac {1}{2k^{2}}}{;$

Theorem 7 showed that the fraction ${displaystyle {frac {h}{k}}}}$ must be a reduced ${displaystyle {sqrt {n}}}$. Any solution to the equation must be in the succession of reduced ${displaystyle {sqrt {n}}}$. This fact, shown by Lagrange, allows solutions, although more theoretical than algorithmic, to the Pell equation.

Quadratic numbers

Unlike the exponential, the square root of 2 is particularly easy to develop in continuous fraction. This property comes from the fact that, from a certain point, we find a full quotient already appeared again. The continuous fraction is periodic from a certain point. The root of 11 has the same property: ${cHFFFF}{cHFFFF}{cHFFFFFF}{cHFFFF}{cHFFFF}{cHFFFFFF}{cHFFFFFF}{3}{cHFFFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFFFF}{cHFF}{cHFF}{cHFF}{cHFF}{cHFF}{$

It follows that a₀ = 3, a₁ = 3, x₀ = 1/2(3 + √11) and x₁ = 3 + √11. We calculate the continued fraction of x₁:

${displaystyle 3+{sqrt {11}}=6+(-3+{sqrt {11}}}})=6+{frac {1}{frac {1}{-3+{sqrt {11}}}}}}}}}=6+{frac {1}{frac {3+{sqrt {11}}}}}{1}}}}}}}}}}}}}}}}}}}}{6+{1$

Note that it is necessary to have a number between 0 and 1, to obtain the continued fraction, from another perspective; see the same calculation...

$♪♪$

It is seen that x₂ is equal to x₀, which allows us to conclude:

${displaystyle {sqrt {11}}=[3;3,6,6,cdots]=[3,{overline {3.6}}}}}}$

The periodicity from a point is proper to the numbers of the form ${displaystyle a+b{sqrt {n}}}$Where ${displaystyle a}$ and ${displaystyle b}$ are rational, ${displaystyle b}$ Not null, and ${displaystyle n}$ an integer that is not perfect square. Regularities are greater for square roots. For example:

${displaystyle {sqrt {19}}=[4,{overline {underbrace {2;1,3,1,2}8}}}}}}}$

Except for the last number of the period, the previous ones form a palindromic number. In addition, the last term of the period is twice the first (in the case discussed, 8, which is twice 4).

Texts for the case

• A. Right. Khinchin; Continued FractionsUniversity of Chicago Press.