 |
Continued Fractions An exploration of finite and infinite continued fractions, and their application in mathematics. Euclid's gcd algorithm, recurring continued fractions and square roots, CFRAC factorisation algorithm, Pell's equation, rational approximation of irrationals, Liouville's transcendental numbers, Khinchin and Levy constants, functions f(x) defined by continued fractions, etc.
|
mathstudio.co.uk |
NEW : I have added a lengthy Section 12 on the Lagrange-Markoff Spectrum.
Continued fractions are fractions in which the denominator is an integer plus another fraction.
This is a review paper 'An Informal Introduction to Continued Fractions'. It introduces several aspects using elementary maths, and is written in a narrative style at the level of the undergraduate student or interested amateur. Many examples are given.
I have been writing this for too long, and it keeps getting longer. Here are the first 140 pages. There will be over 180 pages when I am eventually finished. The section which I have most recently been working on is on the Lagrange-Markoff spectrum -- interesting because of its links to other areas of maths such as quadratic forms, lattices, the torus, etc.
Any given real number, t, can be expressed as a continued fraction by continually repeating the process of extracting the integer part, a, to leave a remainder r < 1, taking the reciprocal of this remainder to be a new number t_1 >1, extracting its integer part, and so on.
If any remainder, r, is zero, the process naturally terminates. Such terminating, finite continued fractions can be evaluated using school arithmetic to give ordinary fractions (rational numbers). On the other hand, non-terminating ones represent irrational numbers.
Irrationals which are square roots have continued fractions with a recurring sequence, similar to the recurring decimals which represent fractions. This finds immediate application in solving Pell's equation x^2 + Ny^2 = 1 for integers x, y, N.
Higher irrationals such as cube and higher roots, and transcendental numbers such as e = exp(1) and pi, have more complicated continued fraction expansions, and this can be developed into a categorisation of real numbers. So continued fractions have found use in number theory.
Perhaps their most spectacular application was in the CFRAC algorithm for factorising large integers, such as the Fermat numbers. F7 was factorised using CFRAC in 1970. I show here how to factorise F5.
The sequence of integers which define the continued fraction (such as 3, 5, and 17 in the picture above) can show some interesting patterns. The article analyses some patterns for finite continued fractions, and then looks at the statistics of occurrence of the digits 1, 2, 3 etc.in irrational numbers. Some powerful techniques in probability and measure theory have been applied to determine representative 'average' values for 'typical' real numbers.
Continued fractions can be generalised by replacing the 3, 5, 17 above by functions of a variable x. This leads to the representation of analytic functions such as log(x) by continued fractions. This was pioneered by Gauss. Other pioneers of continued fractions were Euler, Legendre, and Lagrange.