Periodic continued fraction

Periodic continued fraction

In mathematics, an infinite periodic continued fraction is a continued fraction that can be placed in the form

:x = a_0 + cfrac{1}{a_1 + cfrac{1}{a_2 + cfrac{ddots}{quadddotsquad a_k + cfrac{1}{a_{k+1} + cfrac{ddots}{quadddotsquad a_{k+m-1} + cfrac{1}{a_{k+m} + cfrac{1}{a_{k+1} + cfrac{1}{a_{k+2} + cfrac{1}{ddots},

where the initial block of "k" + 1 partial denominators is followed by a block ["a""k"+1, "a""k"+2,…"a""k"+"m"] of partial denominators that repeats over and over again, "ad infinitum". For example sqrt2 can be expanded to a periodic continued fraction, namely as [1,2,2,2,...] .

The partial denominators {"a""i"} can in general be any real or complex numbers. That general case is treated in the article convergence problem. The remainder of this article is devoted to the subject of regular continued fractions that are also periodic. In other words, the remainder of this article assumes that all the partial denominators "a""i" ("i" ≥ 1) are positive integers.

Purely periodic and periodic fractions

Since all the partial numerators in a regular continued fraction are equal to unity we can adopt a sort of shorthand in which the continued fraction shown above is written as

:egin{align}x& = [a_0;a_1,a_2,dots,a_k,a_{k+1},a_{k+2},dots,a_{k+m},a_{k+1},a_{k+2},dots,a_{k+m},dots] \& = [a_0;a_1,a_2,dots,a_k,overline{a_{k+1},a_{k+2},dots,a_{k+m] end{align}

where, in the second line, a vinculum is used to mark the repeating block.

If the initial non-repeating block is not present – that is, if

:x = [overline{a_0;a_1,a_2,dots,a_m}] ,

the regular continued fraction "x" is said to be "purely periodic". For example, the regular continued fraction for the golden ratio φ – given by [1; 1, 1, 1, …] – is purely periodic, while the regular continued fraction for the square root of two – [1; 2, 2, 2, …] – is periodic, but not purely periodic.

Relation to quadratic irrationals

A quadratic irrational number is an irrational real root of the quadratic equation

:ax^2 + bx + c = 0,

where the coefficients "a", "b", and "c" are integers, and the discriminant, "b"2 − 4"ac", is greater than zero. By the quadratic formula every quadratic irrational can be written in the form

:zeta = frac{P+sqrt{D{Q}

where "P", "D", and "Q" are integers, "D" > 0 is not a perfect square, and "Q" divides the quantity "P"2 − D.

By considering the complete quotients of periodic continued fractions, Euler was able to prove that if "x" is a regular periodic continued fraction, then "x" is a quadratic irrational number. The proof is straightforward. From the fraction itself, one can construct the quadratic equation with integral coefficients that "x" must satisfy.

Lagrange proved the converse of Euler's theorem: if "x" is a quadratic irrational, then the regular continued fraction expansion of "x" is periodic.citation | last1 = Davenport | first1 = H. | title = The Higher Arithmetic | publisher = Cambridge University Press | date = 1982 | page = 104 | isbn = 0521286786] Given a quadratic irrational "x" one can construct "m" different quadratic equations, each with the same discriminant, that relate the successive complete quotients of the regular continued fraction expansion of "x" to one another. Since there are only finitely many of these equations (the coefficients are bounded), the complete quotients (and also the partial denominators) in the regular continued fraction that represents "x" must eventually repeat.


The "conjugate" η of a quadratic surd

:zeta = frac{P + sqrt{D{Q},

is given by

:eta = frac{P - sqrt{D{Q}.,

Reduced surds

The quadratic surd &zeta; is said to be "reduced" if &zeta; > 1 and its conjugate &eta; satisfies the inequalities −1 < &eta; < 0. For instance, the golden ratio &phi; is a reduced surd because its conjugate ½(1 −&radic;5) is greater than −1 and less than zero. On the other hand, the square root of two is not a reduced surd because its conjugate is less than −1.

Galois proved that the regular continued fraction which represents a quadratic surd &zeta; is purely periodic if and only if &zeta; is a reduced surd. In fact, Galois showed more than this. He also proved that if &zeta; is a reduced quadratic surd and &eta; is its conjugate, then the continued fractions for &zeta; and for (−1/&eta;) are both purely periodic, and the repeating block in one of those continued fractions is the mirror image of the repeating block in the other. In symbols we have

:egin{align}zeta& = [overline{a_0;a_1,a_2,dots,a_{m-1] \ [3pt] frac{-1}{eta}& = [overline{a_{m-1};a_{m-2},a_{m-3},dots,a_0}] ,end{align}

where &zeta; is any reduced quadratic surd, and &eta; is its conjugate.

From these two theorems of Galois a result already known to Lagrange can easily be deduced. If "r" > 1 is a rational number that is not a perfect square, then

:sqrt{r} = [a_0;overline{a_1,a_2,dots,a_2,a_1,2a_0}] .,

In particular, if "n" is any non-square positive integer, the regular continued fraction expansion of &radic;"n" contains a repeating block of length "m", in which the first "m" − 1 partial denominators form a palindromic string.

Length of the repeating block

By analyzing the sequence of combinations

:frac{P_n + sqrt{D{Q_n}

that can possibly arise when &zeta; = ("P" + &radic;"D")/"Q" is expanded as a regular continued fraction, Lagrange showed that the largest partial denominator "a""i" in the expansion is less than 2&radic;"D", and that the length of the repeating block is less than 2"D".

More recently, sharper arguments [cite journal|last = Hickerson|first = Dean R.|title = Length of period of simple continued fraction expansion of &radic;d|journal = Pacific J. Math.|volume = 46|date = 1973|pages = 429–432] [cite journal|last = Podsypanin|first = E.V.|title = Length of the period of a quadratic irrational|journal = Journal of Soviet Mathematics|volume = 18|date = 1982|pages = 919–923|doi = 10.1007/BF01763963] based on the divisor function have shown that "L"("D"), the length of the repeating block for a quadratic surd of discriminant "D", is given by

:L(D) = mathcal{O}(sqrt{D}ln{D})

where the big "O" means "on the order of", or "asymptotically proportional to" (see big O notation).

ee also

*Methods of computing square roots#Continued fraction expansion
*Quadratic irrational
*Restricted partial quotients



*cite book|last = Rockett|first = Andrew M.|coauthors = Szüsz, Peter|title = Continued Fractions|publisher = World Scientific|date = 1992|isbn = 981-02-1052-3

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Continued fraction — Finite continued fraction, where a0 is an integer, any other ai are positive integers, and n is a non negative integer. In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the… …   Wikipedia

  • Continued fraction factorization — In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm. It is a general purpose algorithm, meaning that it is suitable for factoring any integer n, not depending on special form or properties.… …   Wikipedia

  • Generalized continued fraction — In analysis, a generalized continued fraction is a generalization of regular continued fractions in canonical form in which the partial numerators and the partial denominators can assume arbitrary real or complex values.A generalized continued… …   Wikipedia

  • Convergence problem — In the analytic theory of continued fractions, the convergence problem is the determination of conditions on the partial numerators ai and partial denominators bi that are sufficient to guarantee the convergence of the continued fraction This… …   Wikipedia

  • Restricted partial quotients — In mathematics, and more particularly in the analytic theory of regular continued fractions, an infinite regular continued fraction x is said to be restricted , or composed of restricted partial quotients , if the sequence of denominators of its… …   Wikipedia

  • Quadratic irrational — In mathematics, a quadratic irrational, also known as a quadratic irrationality or quadratic surd, is an irrational number that is the solution to some quadratic equation with rational coefficients. Since fractions can be cleared from a quadratic …   Wikipedia

  • Complex plane — Geometric representation of z and its conjugate in the complex plane. The distance along the light blue line from the origin to the point z is the modulus or absolute value of z. The angle φ is the argument of z. In mathematics …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Vinculum (symbol) — A vinculum is a horizontal line placed over a mathematical expression, used to indicate that it is to be considered a group. Vinculum is Latin for bond , fetter , chain , or tie , which is roughly suggestive of some of the uses of the… …   Wikipedia

  • Trigonometric functions — Cosine redirects here. For the similarity measure, see Cosine similarity. Trigonometry History Usage Functions Generalized Inverse functions …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”