A Brief Introduction to Continued Fractions
In its most general form, a continued fraction can be written as such:
where {an} and {bn} are infinite sequences of integers. If the sequences are finite, or end, the whole expression can be evaluated to a rational number, which takes the form of p/q where p/q are integers. We call b0 the integral part, or the integer part, of the fraction.
Finite Continued Fractions
Let's take 9/6 as an example. We can use the Euclidean Algorithm which has the form of:
9 = q0*6 + r0 where q0 = 1 and r0 = 3
6 = q1*3 + r1 where q1 = 2 and r1 = 0
since r1 = 0, we can stop the algorithm. Many people's introduction to this algorithm is for the purpose of finding the greatest common divisor/factor but here, we will use it to construct our finite continued fraction.
Taking the terms of the sequences {qn} to be our sequence of partial denominators, {bn}, and {rn} to be our sequence of partial numerators, {an} we get the following:
I strongly suggest repeating this process by yourself with other positive, rational numbers. Since integers are a subset of rational numbers, where they are in the form of q/1 where q is an integer, integers are the most trivial cases of continued fractions -- a fraction.
Remark: to find the continued fraction form of 6/9, we shift all the terms over by one place and set the b0 term to 0.
So far, we have only dealt with finite continued fractions -- what about infinite continued fractions?
Infinite Continued Fractions
Let's take a small detour to explain real numbers and how one can construct the reals.
In my Sequences and Series class, which was later renamed to Introduction to Mathematical Analysis, we proved that the set of real numbers can be constructed from a Cauchy sequence of rational numbers. I will spare you from the proof of such but in summary, say we have π, which is an irrational number, we can have a sequence of increasingly close approximations:
an = [3, 3.1, 3.14, 3.141, 3.1415, ...]
Notice how each term is truncated; this implies that each of these can be written in the form of a rational number.
an = [3/1, 31/10, 157/50, ...]
note: as much as I would *love* to write all of those fractions out, I am lazy :D
We've already seen that it is possible to write rational numbers as continued fractions and since the limit of the given sequence is π, we can write π as an infinite continued fraction approximation.
This is π's simple continued fraction approximation. What makes it simple is that for all n, an = 1. This allows us to write our continued fractions in the form of a list:
π = [3; 7, 15, 1, 292, 1, 1, ...]
Remark: Despite each example here being a simple continued fraction, there are many out there that are NOT simple. However, every real number does have a simple continued fraction form.
More About Continued Fractions
For a more in-depth and rigorous introduction that is also directed towards beginners, I recommend looking at these notes which were made for a short course on continued fractions by Dr. Gautam Gopal Krishnan.
A more analytical approach by Dr. Swastik Kopparty for his Algorithmic Number Theory class can be found here.
I used both of these as initial readings for a project with my school's Mathematics department and found them both very helpful.
I am currently participating in a Directed Reading Program and the topic I am reading about is, you guessed it, continued fractions. It has turned less into a reading project and more of a light research project but either way, I'm having loads of fun.
I might share the Github repo for it towards the end of the semester but for now, it shall stay private.
Feel free to ask questions!
yousharknotpass
turnnoffyourmind
jacobvanloon
romaincrisis
snowghoul
origamiaround
baratheonpilled