Fractals/Continued fraction

            "Do not worry about your problems with mathematics, I assure you mine are far greater." Albert Einstein

Notation

Generalized form

A continued fraction is an expression of the form

$a_0+\frac{b_1}{a_1+\frac{b_2}{a_2+\frac{b_3}{a_3+{}_{\ddots }}}}$

where :

• $a_n$ and $b_n$ are either integers, rational numbers, real numbers, or complex numbers.
• $a_0$, $a_1$ etc., are called the coefficients or terms of the continued fraction

Variants or types :

• If $b_n=1$ for all $n$ the expression is called a simple continued fraction.
• If the expression contains a finite number of terms, it is called a finite continued fraction.
• If the expression contains an infinite number of terms, it is called an infinite continued fraction.

Thus, all of the following illustrate valid finite simple continued fractions:

Examples of finite simple continued fractions

Formula	Numeric	Remarks
$a_0$	$2$	All integers are a degenerate case
$a_0+\frac{1}{a_1}$	$2+\frac{1}{3}$	Simplest possible fractional form
$a_0+\frac{1}{a_1+\frac{1}{a_2}}$	$-3+\frac{1}{2+\frac{1}{18}}$	First integer may be negative
$a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}$	$\frac{1}{15+\frac{1}{1+\frac{1}{102}}}$	First integer may be zero

simple form

It is generally assumed that the numerator b of all of the fractions is 1. Such form is called a simple or regular continued fraction, or said to be in canonical form.

If real number is a fraction ( x < 1), then $a_0$ is zero and the notation is simplified:

  $[0;a_1,a_2,a_3]=[a_1,a_2,a_3]$

Finite

Notation :

 $a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}=[a_0;a_1,a_2,a_3]$

Every finite continued fraction represents a rational number $\frac{p}{q}$:

  $\frac{p}{q}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}=[a_0;a_1,a_2,a_3]$

If positive real fraction x is rational number, there are exactly two different continued fraction expansions:

  $[a_1,a_2,a_3,...,a_n]=[a_1,a_2,a_3,...,a_n-1,1]$

where

• $a_n>1$
• Usually the first, shorter form is chosen as the canonical representation
• second form is one longer then the first

Infinite

Notation :

 $a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\ddots }}}=[a_0;a_1,a_2,a_3,\dots ]$

Every infinite continued fraction is irrational number $\alpha$ :

 $\alpha =a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\ddots }}}=[a_0;a_1,a_2,a_3,\dots ]$

The rational number $\frac{p_n}{q_n}$ obtained by limited number of terms in a continued fraction is called a n-th convergent

  $\frac{p_n}{q_n}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\ddots +\frac{1}{a_n}}}}}=[a_0;a_1,a_2,a_3,\dots ,a_n]$

because sequence of rational numbers $\frac{p_n}{q_n}$ converges to irrational number $\alpha$

 $\underset{n\to \mathrm{\infty }}{\lim }\frac{p_n}{q_n}=\alpha$

In other words irrational number $\alpha$ is the limit of convergent sequence.

Nominator p and denominator q can be found using the relevant recursive relation:

$p_n=a_n{p}_{n-1}+p_{n-2}$

$q_n=a_n{q}_{n-1}+q_{n-2}$

so

$\frac{p_n}{q_n}=\frac{a_n{p}_{n-1}+p_{n-2}}{a_n{q}_{n-1}+q_{n-2}}$

Key words :

• the sequence of continued fraction convergents $\frac{p_n}{q_n}$ of irrational number $\alpha$
• sequence of the convergents
• continued fraction expansion
• rational aproximation of irrational number
• a best rational approximation to a real number r by rational number p/q

How to use it in computer programs

• decimal number ( real or rational) to continued fraction
  • abacus CAS
  • Maxima CAS : cf (expr) Converts expr into a continued fraction.

Maxima CAS

In Maxima CAS one have cf and float(cfdisrep())

(%i2) a:[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
(%o2) [0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
(%i3) t:cfdisrep(a)
(%o3) 1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/1))))))))))))))))))))))
(%i4) float(t)
(%o4) 0.618033988957902

To compute n-th convergent:

(%i10) a;
(%o10) [0, 3, 2, 1000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
(%i11) a3: listn(a,3);
(%o11) listn([0, 3, 2, 1000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
                                                                         1], 3)
(%i12) a3: firstn(a,3);
(%o12)                             [0, 3, 2]
(%i13) cf3:cfdisrep(a3);
                                       1
(%o13)                               -----
                                         1
                                     3 + -
                                         2
(%i14) r3:ratsimp(cf3);
                                       2
(%o14)                                 -
                                       7
(%i15) 

Examples

• number theory
  • aproximation of irrational number, see rotation number in case of Siegel disk
• continued fractions based functions over the complex plan
• " a continued fraction may be regarded as a sequence of Möbius maps" Alan F. Beardone

Help

• math.stackexchange questions tagged continued-fractions
• mathoverflow questions tagged continued-fractions
• Continued Fractions - Professor John Barrow
• Chaos in Numberland: The secret life of continued fractions By John D. Barrow

See also

• binary expansion ( representation of real number)
• fractional iteration
• dynamics of continued fractions
  • Dynamics of continued fractions and kneading sequences of unimodal maps by Claudio Bonanno, Carlo Carminati, Stefano Isola, Giulio Tiozzo

References

• CALENDARS AND CONTINUOUS FRACTIONS by Anne Broise ( in fr.)
• Dynamics of continued fractions and kneading sequences of unimodal maps by Claudio Bonanno, Carlo Carminati, Stefano Isola, Giulio Tiozzo