PlanetMath: continued fraction

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (191)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

continued fraction

(Definition)

Given a sequence of positive real numbers $(a_n)_{n \ge 1}$ , with any real number. Consider the sequence

$\displaystyle c_1$	$\displaystyle =a_0+\frac {1}{a_1}$
$\displaystyle c_2$	$\displaystyle =a_0+\frac {1}{a_1+\frac {1}{a_2}}$
$\displaystyle c_3$	$\displaystyle =a_0+\frac {1}{a_1+\frac {1}{a_2+\frac {1}{a_3}}}$
$\displaystyle c_4$	$\displaystyle =\ldots$

The limit of this sequence, if it exists, is called the value or limit of the infinite continued fraction with convergents , and is denoted by

$\displaystyle a_0 + \frac {1}{a_1 + \frac {1}{a_2 + \frac {1}{a_3 + \ldots}}}$

or by

$\displaystyle a_{0} + \frac{1}{a_{1} + }\frac{1}{a_{2} + }\frac{1}{a_{3} + }\ldots$

In the same way, a finite sequence

$\displaystyle (a_n)_{1\le n\le k}$

defines a finite sequence

$\displaystyle (c_n)_{1\le n\le k}\;.$

We then speak of a finite continued fraction with value

An archaic word for a continued fraction is anthyphairetic ratio.

If the denominators are all (positive) integers, we speak of a simple continued fraction. We then use the notation $q = \langle a_0; a_1, a_2, a_3,\ldots \rangle$ or, in the finite case, $q = \langle a_0; a_1, a_2, a_3, \ldots , a_n \rangle \;.$

It is not hard to prove that any irrational number is the value of a unique infinite simple continued fraction. Moreover, if denotes its th convergent, then is an alternating sequence and $\vert c - c_n\vert$ is decreasing (as well as convergent to zero). Also, the value of an infinite simple continued fraction is perforce irrational.

Any rational number is the value of two and only two finite continued fractions; in one of them, the last denominator is 1. E.g.

$\displaystyle \frac{43}{30} = \langle 1;2,3,4 \rangle = \langle 1;2,3,3,1 \rangle \;.$

These two conditions on a real number are equivalent:

1. is a root of an irreducible quadratic polynomial with integer coefficients.

2. is irrational and its simple continued fraction is “eventually periodic”; i.e.

$\displaystyle c=\langle a_0;a_1,a_2,\ldots\rangle$

and, for some integer

and some integer

, we have $a_n=a_{n+k}$ for all $n\ge m$ .

For example, consider the quadratic equation for the golden ratio:

$\displaystyle x^2 = x + 1$

or equivalently

$\displaystyle x = 1 + \frac{1}{x}\;.$

We get

$\displaystyle x$	$\displaystyle =$	$\displaystyle 1 + \frac {1}{1+\frac {1}{x}}$
	$\displaystyle =$	$\displaystyle 1 + \frac {1}{1+\frac {1}{1+\frac {1}{x}}}$

and so on. If , we therefore expect

$\displaystyle x = \langle 1; 1, 1, 1, \ldots \rangle$

which indeed can be proved. As an exercise, you might like to look for a continued fraction expansion of the other solution of

Although is transcendental, there is a surprising pattern in its simple continued fraction expansion.

$\displaystyle e=\langle 2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, \ldots \rangle$

No pattern is apparent in the expansions some other well-known transcendental constants, such as $\pi$ and Apéry's constant $\zeta(3)$ .

Owing to a kinship with the Euclidean division algorithm, continued fractions arise naturally in number theory. An interesting example is the Pell diophantine equation

$\displaystyle x^2 - Dy^2 = 1$

where

is a nonsquare integer

. It turns out that if

is any solution of the Pell equation other than $(\pm 1, 0)$ , then $\vert \frac{x}{y}\vert$ is a convergent to $\sqrt{D}$ .

$\frac{22}{7}$ and $\frac{355}{113}$ are well-known rational approximations to $\pi$ , and indeed both are convergents to $\pi$ :

$\displaystyle 3.14159265\ldots$	$\displaystyle =$	$\displaystyle \pi = \langle 3;7,15,1,292,...\rangle$
$\displaystyle 3.14285714\ldots$	$\displaystyle =$	$\displaystyle \frac{22}{7} = \langle 3;7\rangle$
$\displaystyle 3.14159292\ldots$	$\displaystyle =$	$\displaystyle \frac{355}{113} = \langle 3;7,15,1\rangle=\langle 3;7,16\rangle$

For one more example, the distribution of leap years in the 4800-month cycle of the Gregorian calendar can be interpreted (loosely speaking) in terms of the continued fraction expansion of the number of days in a solar year.

"continued fraction" is owned by PrimeFan. [ full author list (5) | owner history (4) ]

(view preamble)

Other names:

chain fraction

Also defines:

anthyphairetic ratio, simple continued fraction

Keywords:

number theory, rational number, irrational number, Pell

Attachments:: Farey sequence (Definition) by ariels
method for computing simple continued fractions with the aid of calculator and pencil and paper (Algorithm) by PrimeFan

Log in to rate this entry.
(view current ratings)

Cross-references: number, approximations, rational, Pell equation, Diophantine equation, number theory, division algorithm, Euclidean, Apéry's constant, transcendental, solution, golden ratio, quadratic equation, coefficients, polynomial, irreducible, root, equivalent, rational number, decreasing, alternating, irrational number, integers, denominators, finite, finite sequence, convergents, infinite, limit, real numbers, positive, sequence
There are 28 references to this entry.

This is version 26 of continued fraction, born on 2002-06-12, modified 2008-06-10.
Object id is 3101, canonical name is ContinuedFraction.
Accessed 15991 times total.

Classification:

AMS MSC:	11A55 (Number theory :: Elementary number theory :: Continued fractions)
	11J70 (Number theory :: Diophantine approximation, transcendental number theory :: Continued fractions and generalizations)
	11Y65 (Number theory :: Computational number theory :: Continued fraction calculations)

Pending Errata and Addenda

None.[ View all 9 ]

Discussion

forum policy

Interact