 |
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, rates of convergence, Lagrange-Markoff spectrum, Liouville's transcendental numbers, Gauss-Khinchin probability distribution, functions f(x) defined by continued fractions, etc.
|
mathstudio.co.uk |
Download the whole 200 pages here.
Continued fractions are fractions in which the denominator is an integer plus another fraction, as in the example above..
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. The article is in five Parts covering many aspects of maths.
The fraction above evaluates to 275/361. The process can be reversed and any 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.
For example, 275/361 = 1/(365/275) = 1/(1 + 86/275). Then invert again and find 275/86 = 3+17/86, then finally 86/17 = 5+1/17.
If any remainder, r, is zero, the process naturally terminates as in the example. 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.
Those 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 e^x and log(x+1) by continued fractions. This was pioneered by Gauss who made some spectacular mathematical discoveries. Other pioneers of continued fractions were Euler, Legendre, and Lagrange.