Transcript PowerPoint presentation for "Continued Fractions"

Continued Fractions
John D Barrow
Headline in Prairie Life
Decimals
 = 3.141592…
= i ai 10-i
 = (ai) = (3,1,4,1,5,9,2,…)
But rational fractions like 1/3 = 0.33333..
do not have finite decimal expansions
Why choose base 10?
Hidden structure?
A Different Way of Writing Numbers
x2 – bx – 1 = 0
x = b + 1/x
Substitute for x on the RH side
x = b + 1/(b +1/x)
Do it again…and again…
b = 1 gives the golden mean
x =  = ½(1 + 5) = 1·6180339887..
William Brouncker
First President of the Royal Society
Introduced the ‘staircase’ notation
(1620-84)
by using Wallis’ product formula for 
John Wallis
Wallis: ‘continued fraction’ (1653-5)
(1616-1703)
Euler’s Formula
Log{(1+i)/(1-i)} = i/2
i = -1
Avoiding the Typesetter’s Nightmare
x  [a0 ; a1, a2, ……]
cfe of x
Rational numbers have finite cfes
Take the shortest of the two possibilities
for the last digit eg ½ = [0;2] not [0;1,1]
Irrational numbers have a (unique)
infinite cfes
Pi and e
 = [3;7,15,1,292,1,1,3,1,14,2…..]
e = 2.718…. = [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,….]
 = [1;1,1,1,1,1,1,1,……..]
2 = [1;2,2,2,2,2,2,2,2,2,2,….]
golden ratio
Cotes (1714)
3 = [1;1,2,1,2,1,2,1,2,1,2,1,.]
‘Noble’ numbers end in an infinite sequence of 1’s
Plot of the cfe digits of
Rational Approximations for Irrational Numbers
Ending an infinite cfe at some point creates
a rational approximation for an irrational number
 = [3;7,15,1,292,1,1,…]
Creates the first 7 rational approximations for 
labelled pn/qn
3, 22/7, 333/106, 355/113, 103993/33102, 104384/33215,
208341/66317,…
A large number (eg 292) in the cfe expansion creates a very good a
Better than Decimals
Truncating the decimal expn of  gives 31415/1000 and 314/100
The denominators of 314/100 and 333/106 are almost the same,
but the error in the approximation 314/100 is 19 times as large as
the error in the cfe approx 333/106.
As an approximation to , [3; 7, 15, 1] is more than one hundred times
more accurate than 3.1416.
 = (2143/22)1/4 is good to 3 parts in 104 !
Ramanujan knew that 4 = [97;2,2,3,1,16539,1,…]
Note that the 431st digit of  is 20776
Minding your p’s and q’s
As n increases the rational approximations to any
irrational number, x, get better and better
x – pn/qn   0
In the limit the best possible rational approx is
x – p/q  <1/(q25)
qk > 2(k-1)/2
The golden ratio  is the most irrational number: it
lies farthest from a rational approximation 1/(q25)
Approximants are 5/3, 8/5, 13/8, 21/13,…
They all run close to this boundary
Same is true for all (a + b)/(c + d) with ad – bc = + 1
Getting Your Teeth Into Gears
The ratio of the numbers of teeth on two cogs governs their speed
Mesh a 10-tooth with a a 50 tooth and the 10-tooth will rotate 5 time
quicker (in the opposite direction).
What if we want one to rotate 2 times faster than the other.
No ratio will do it exactly.
Cfe rational approximations to 2 are 3/2, 7/5, 17/12, 41/29, 99/70,
So we could have 7 teeth on one and 5 on the other
(too few for good meshing though) so use 70 and 50.
If we can use 99 and 70 then the error is only 0.007%
Scale Models
of
the Solar System
Gears Without Tears
In 1682 Christian Huygens used 29.46 yrs for Saturn’s orbit around Sun (now
29.43)
Model solar system needs two gears with P and Q teeth: P/Q  29.46
Needs smallish values of P and Q (between 20 and 220) for cutting
Find cfe of 29.46. Read off first few rational approximations
29/1, 59/2, 206/7,..then simulate Saturn’s motion relative to Earth
by making one gear with 7 teeth and one with 206
Carl Friedrich Gauss
(1777-1855)
Probability and Continued Fractions
Any infinite list of numbers defines a unique real number by its cfe

There can’t be a general frequency distribution for the cfe of all
numbers
But for almost every real number there is !
The probability of the appearance of the digit k in the cfe of
almost every number is
P(k) = ln[ 1 + 1/k(k + 2) ]/ln[2]
P(1) = 0.41, P(2) = 0.17, P(3) = 0.09, P(4) = 0.06, P(5) = 0.04
P(k)  1/k2 as k 
ln(1+x)  x
Typical Continued Fractions
Arithmetic mean (average) value of the k’s is
k=1 k P(k)  1/ln[2]  k=1 1/k  
Geometric mean is finite and universal for a.e number
(k1........kn)1/n  K= 2.68545….. as n  
K k=1 {1+1/k(k+2)}ln(k)/ln(2) : Khinchin’s constant
Captures the fact that the cfe entries are usually small
e = 2.718.. is an exception
(k1........kn)1/n = [2N/3(N/3)!]1/N  0.6259N1/3  
k=11/k has an Infinite Sum
 = 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 + 1/11 + .......
 = 1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 + 1/10 + 1/11 +…..1/15) +..
 > 1/2 + (1/4 + 1/4) +(1/8 + 1/8 + 1/8 + 1/8) + (1/16 + 1/16 + 1/16 + 1/16 + ..+ 1/16
 > 1/2 + 1/2 + 1/2 + 1/2 + …….  
“Divergent series are the invention of the devil,
and it is a shame to base on them any demonstration whatsoever”
Niels Abel
Geometric Mean for the cfe Digits of 
G Mean
K =2.68..
k
Aleksandr Khinchin
1894-1959
Geometric Means for Some Exceptional Numbers
Slow Convergence to K-- with a pattern ?
Geo Mean
Cfe geometric means for , 2, , log(2), 21/3, 31/3
Lévy’s Constant
If x has a rational approx pn/qn after
n steps of the cfe, then for almost
every number
qn < exp[An] as n   for some A>0
qn1/n  L = 3.275… as n  
Paul Lévy, 1886-1971
L
for cfe of 
3.275…
A Strange Series
What is the sum of this series??
S(N) = p=1
N
N
1/{p3sin2p}
(Pickover-PetitMcPhedran problem)
S(N)
22
4.75410
26
4.75796
28
4.75873
310
4.80686
313
4.80697
314
4.80697
355
29.4 !!
Occasionally p  q so sin(n)  0 and S 
This happens when p/q is a rational approx to 
3/1, 22/7, 333/106, 355/113,
103993/33102, 104384/33215,
208341/66317,…
Dangerous values continue forever
and diverge faster than 1/p3
Chaos in Numberland
Generate the cfe of
u = k + x = whole number + fractional part = [u] + x
 = 3 + 0.141592.. = k1 + x1
k2 = [1/x1] = [7.0625459..] = 7
x2 = 0.0625459..
k3 = [1/x2] = [15.988488..] = 15
The fractional parts change from x1 x2  x3 ..
chaotically. Small errors grow exponentially
Gauss’s Probability Distribution
xn+1 = 1/xn – [1/xn]
As n   the probability of outcome x tends to
p(x) = 1/[(1+x)ln2] : 01 p(x)dx = 1
Error is < (0.7)n after n iterations
p(x)
In a
Letter to Laplace
30th Jan 1812
‘a curious problem’
that had occupied him
for 12 years
Distribution of
the fractional
parts
x
xn+1 = 1/xn – [1/xn] = T(xn)
T(x)
T(x) =1/x – k
(1-k)-1<x<k-1
ldT/dxl = 1/x2 > 1
as 0 < x < 1
x
n steps = initial  exp[ht]: h = 2/[6(ln2)2]  3.45
The Mixmaster Universe
The Continued-Fraction Universe
u = 6.0229867.. = k + x = 6 + 0.0229867..
u  1/x = 1/0.0229867 = 43.503417 = 43 + 0.503417
u 1/0.503417 = 1.9864248 = 1 + 0.9864248
Next cycles have 1, 72, 1 and 5 oscillations respectively
To be continued……