  # Ken Ward's Mathematics Pages

## Number Theory Continued Fractions

Number Theory Contents

## Idea of Continued Fractions

Once again, we aren't embarrassed to begin with trivial examples. The first two examples are trivial and the third isn't.
If we a decimal number, say 0.5, we can express it as:
0.5= [1.1]
That is as a double reciprocal (a=1/1/a).

And by evaluating the lower fraction, 1/0.5, we get:
0.5=1/2,
which is the fractional expression for 0.5.

As it happens, the reciprocal of 0.5 is 2, that is, the calculation works out even because the fraction terminates quite quickly.

If we take 0.75 as our new decimal, then we will need to continue the fraction:
0.75= [1.2]

0.75 goes once into 1 and leaves a remainder 0.25. That is 1/0.75=1+0.25/0.75
0.75= [1.3]

Writing 0.25/0.75 as a double reciprocal: 1/1/0.25/0.75=1/0.75/0.25
0.75= [1.4]
Because 0.75/0.25=3, the fraction terminates, and we have:
0.75= [1.5]

We need to work out the final fraction. And beginning at the bottom, we have 1+1/3=4/3. And 1/(4/3)=3/4, which as know is the fractional representation of 0.75.

Our next problem is to convert 0.5385 to a fraction.
The first double reciprocal:
0.5385= [1.6]

0.5385=1+1/1/0.8571
0.5385= [1.7]

1/0.8571=1+1/0.1667 (we note something that is going to work out soon!)
0.5385= [1.8]

1/0.1667=6 (to 4 decimal places. See below), so:
0.5385= [1.9]

Working out the fraction from the bottom 1+1/6=7/6. 1+1/7/6=13/7. And finally, 1/13/7=7/13.

So 0.5385=7/13 (to 4 decimal places)

#### A note on accuracy

[This note isn't particularly about continued fractions, but about using approximations in the calculations.]

Previously, our continued fractions terminated accurately. Here, I have worked to 4 decimal places with a calculator, and the continued fraction terminated, and gave us 7/13. To 4 decimal places, 1/0.1667=6, but this is an approximation.

Window's calculator gives 9/13=0.538461... and rounded to 4 places is 0.5385.

## Infinite, Finite, Convergent and Divergent Continued Fractions

1/4, can be written as a continued fractions as:
[0,4]
where the 0 shows there is not integer part and the 4 is the first denominator. So:
1/4=[0,4]
1/4 forms a finite continued fraction because the number of terms is finite (actually 2).

Continued fractions of irrational numbers are infinite, because the number of terms never ends. For instance, the continued fractions for π and √2 are infinite.

Nonetheless for the continued fraction being infinite, or finite, it may converge or diverge. It diverges when the resulting fractions oscillate or become infinite. Otherwise, it converges when the values of the continued fraction approach a limit.

For instance, the continued fraction √2=[1,2,2...], is infinite, but converges to a value.

A regular continued fraction is one where all the terms are natural numbers, except the first, which can be zero. Regular continued fractions always converge.

## Recursion Formula

The following recursion formula applies to continued fractions: [3.1]
For instance,
π=[3, 7, 15, 1, 292...]
=3+1/[7, 15, 1, 292...]
=3+1/(7+1/[15, 1, 292...])
=3+1(7+1/(15+1/([1, 292...]) )

## Computing Continued Fractions

We seek the continued fraction for a number α. First: [4.1]
Where [α] means the floor of α (the greatest integer less than alpha, using Gaussean brackets). r1 is the remainder.
Set a0=[α]

Next [4.2]

In general: [4.3]
The algorithm stops when the remainder is zero. This is true when integers are used, but not when decimals are used, because of rounding errors.

#### Example 1

We seek the contined fraction for α=23/17
23/17=1+6/17
17/6=2+5/6
6/5=1+1/5
5=5+0

The algorithm stops at zero. The continued fraction for 23/17 is [1,2,1]

#### Example 2

α=1.71
Working to 4 decimal places:

1.71=1+0.71
1/0.71=1+0.4085
1/0.4085=2+0.4483
1/0.4483=2+0.2308
1/0.2308=4+0.3333
1/0.3333=3+0
The continued fraction is [1,1,2,2,4,3]

## Computing Continued Fractions Using a Calculator

The only point here is that when working with decimals, errors may prevent the algorithm from reaching zero, at least in a reasonable number of steps.
We seek the continued fraction for 3.1415926536, which is pi to 10 decimal places.

In the following table, a is the term of the continued fraction, and r is the fractional remainder.

k ak rk Remarks
1 3 0.1415926536 First, we write the integer part, 3, under a and the fraction remaining under r.
2 7 0.0625133054 Take the reciprocal of r1, and write the integer part under a2, and the fraction under r2.
3 15 0.9965945426 We continue, taking the reciprocal of r2 and writing the integral part under a3 and the fraction under r3.
4 1 0.0034170942
5 292 0.6463074972
6 1 0.5472511217
7 1 0.8273146648
The continued fraction for 3.1415926536 is [3,7,15,1,292,1,1]. For reasons not explained here, but explained later, we cannot go further with our calculations because the error in the fraction becomes less than the expected error in our original number, so we find ourselves chasing rounding errors, rather than obtaining a more accurate representation of the number.

[3,7,15,1,292,1,1] is an approximation to the continued fraction for pi (the true continued fraction is infinite, of course).

As it happens, the above table was written by a spreadsheet, not a calculator!

## Notation

Here are some definitions related to continued fractions, to assist talking about them. (I have tended to be informal in these pages).
A representation of a number, α, as a continued fraction: is called a representation in canonical form. a0, a1, etc are called terms.

An infinite continued fraction is one with an infinite number of terms (the number, α is then an irrational number).

A finite continued fraction is one with a finite number of terms. The number, α, is therefore a rational number.

The value pk/qk is called the canonical approximation, or the k-th convergent.

The values pk and qk are called the k-th iteration (of p or q).

For the sake of clarification, a recursion produces a new value from previous values. A recrusive formula produces new values from previous ones. An iteration produces an updated value. An iterative formula produces an updated value from a previous one, usually more accurate. The difference between iteration and recursion is not always clear. The p's and k's are called iterations because they are updated, more accurate values for the numerator and the denominator. The recursive formula above, produces new terms for the continued fraction from previous values.

Number Theory Contents

Ken Ward's Mathematics Pages

# Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com 