10/24/2018 elementary number theory - What are the applications of continued fractions?

- Mathematics Stack Exchange

What are the applications of continued Ask Question

fractions?

What is the most

motivating way to introduce
continued fractions? Are
there any real life
applications of continued
fractions?

elementary-number-theory

continued-fractions

motivation

edited May 2 '15 at 13:19

VividD
8,217 5 44 92

asked Nov 29 '13 at 13:29

user92877
441 1 6 11

4 My junior high math

teacher (R.I.P., Heikki, I
owe you much) wanted to
keep me occupied, and
gave me the summer
assignment to find the
rational number m/n,
0 < n < 10000 closest to

π. – Jyrki Lahtonen Nov 29

'13 at 13:43

4 Convergents of simple
continued fractions give
you best rational
approximations. You can
use the simple continued
−
−
fraction of √d to solve
Pell's equation
= ±1. Also, you
2 2
x − dy

can prove that π and e are

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 1/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange
irrational. The RSA
application Alexander
Gruber is thinking about
might be this one:
en.wikipedia.org/wiki/Sho
r's_algorithm (step 5 in
"Quantum part") – spin
Apr 23 '14 at 6:08

10 Answers

There are at least three

integer factorization
algorithms based (one way
or other) on properties of
continued fractions. The
one by Lehman is a fairly
elementary (but delightfully
clever) deterministic
method.

1. Shanks
2. Brillhart and Morrison
3. Lehman

answered Apr 27 '14 at 6:30

WimC
23.9k 2 28 60

One very nice elementary

application is Gosper's
batting average problem: if
a baseball player's (3-digit
rounded) batting average is
.334 , what's the smallest

number of at-bats that

player could have? (Batting
average is computed as
(number of hits)/(at-bats).)

The solution proceeds by

noting that a rounded
average of .334 corresponds
to an actual number in the
range [.3335, .3345) ;
finding the continued
fractions for these values

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 2/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

yields
.3335 = 667/2000 = [0; 2,

and
.3345 = 669/2000 = [0; 2,

. This implies that the

'simplest' number within
the range is
96
[0; 2, 1, 95] = ≈ 0.3344
287

answered Apr 23 '14 at 23:01

Steven Stadnicki
40.6k 7 67 121

There is this interesting

article about the application
of continued fractions in
Phyllotaxis, the research on
leaves, which I found pretty
interesting. Maybe you can
find more over google?

edited Apr 23 '14 at 22:47

Alexander Gruber ♦
20.1k 24 102 171

answered Nov 29 '13 at 13:35

BIS HD
1,937 11 27

Why the downvote? I think

I helped the OP?! –
BIS HD Apr 23 '14 at
19:48

Oh hey, sorry, I think that

was me. I misclicked while
trying to upvote. :) It is
fixed. –
Alexander Gruber ♦ Apr
23 '14 at 22:48

Haha, thanks for the

clearing :-) – BIS HD Apr
24 '14 at 16:53

Since no one mention it, I

think it's really pleasant
https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 3/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

knowing that every rational

tangle correspond to some
continued fraction(Conway
showed that).

For further information see:

An Enumeration of
Knots and Links, and
Some of Their
Algebraic Properties by
Conway
Another proof On the
classification of
rational tangles

Here is good expository

article:

The Power of
Mathematics by
Conway
Conway’s Rational
Tangles, a good
educational article

Note:Image source:
http://rationaltangle.wordp
ress.com/what-are-
tanglesrational-tangles/

edited Apr 26 '14 at 14:51

answered Apr 26 '14 at 14:44

SomeOne
651 5 14

Here are some

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 4/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

properties/uses that might

be used to motivate an
investigation of Continued
Fractions:

1. Surprisingly good
rational
approximations to real
numbers
2. Finite for rational
numbers and repeating
for quadratic algebraic
numbers
3. Used to solve linear
Diophantine equations
4. Used to solve Pell-type
equations

Continued fractions are

extremely good rational
approximations to real
p
numbers. If is a q

continued fraction
approximation for the real
number r , we have

∣ p ∣ 1
∣ − r∣ ≤ (1)
2
∣ q ∣ q

Furthermore, if we have

∣ p ∣ 1
∣ − r∣ ≤ (2)
2
∣ q ∣ 2q

p
then q
is a continued
fraction approximation for
r.

In this manner, continued

fractions offer the best
rational approximations to
real numbers.

The continued fraction for a

real number r terminates if
and only if r is rational.
Furthermore, the continued
fraction for a real number r

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 5/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

is periodic if and only if r is

not rational and
ar + br + c = 0 where
2

a, b, c ∈ Z are not all 0.

p
Successive convergents, q
j

p
and q
j+1
of a continued
j+1

fraction have the property

pj qj+1 − qj pj+1 = (−

Note that (3) implies

j
pj pj+1 (−1)
− =
qj qj+1 qj qj+1

Thus, successive
convergents alternate above
and below their limit. (4)
shows why (1) is true.

Given a, b ∈ Z relatively
prime, (3) is very useful in
solving the Diophantine
equation

ax + by = 1 (5)

For example, we can solve

23x + 17y = 1 by

computing the continued

fraction for : 23

17

23 1
= 1 +
17 1
2 +
1
1 +
5

The next to last convergent

is :4

4 1
= 1 + (7)
3 1
2 +
1

thus, (3) says

4 ⋅ 17 − 3 ⋅ 23 = −1

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 6/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

Therefore, we have the

solution

3 ⋅ 23 − 4 ⋅ 17 = 1 (9

The accuracy of Continued

Fraction approximations
allow the solution of Pell's
equation. For example,
consider the continued
–
fraction for √3:

rep

–
√3 = (1, 1, 2, 1, 2, 1

p –
Since ∣∣ q
− √3∣
∣ ≤
1

2
, we
q

have

∣ p2 − 3q 2 ∣ = |p − q√
∣ ∣

1
≲ ⋅ 2q√
q
–
= 2√3

Thus, no matter how big p

and q get, p − 3q is2 2

bounded; in fact, it is
periodic. The sequence of
convergents for (10) is

1 2 5 7 19 26
, , , , , ,
1 1 3 4 11 15

and the sequence of

p − 3q is
2 2

−2, 1, −2, 1, −2, 1, −

Thus, the convergents in

red give solutions for the
Pell equation
= 1.
2 2
p − 3q

edited Apr 26 '14 at 15:59

answered Apr 24 '14 at 9:19

robjohn ♦
261k 27 300 618

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 7/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

These may not be the best

ways to motivate continued
fractions, but here are some
applications.

There is a well-known
method for "encoding" a
geodesic on the modular
surface via continued
fractions by looking at the
continued fraction
expansions of the
"endpoints" of the geodesic
on the real line. Studying
the continued fraction
associated to a geodesic is
one way of understanding
how the geodesic "winds
around" the surface. For
example, if the continued
fractions are periodic, then
the geodesic will be periodic
(a closed loop) as well. If
the sequences of integers
appearing in the continued
fraction expansion contain
all finite sequences of
integers, then the geodesic
is dense. To my knowledge
the first time this is used is
in an old paper of Emil
Artin, Ein mechanisches
System mit
quadiergodischen Bahnen.
This idea is expanded upon
and clarified in a series of
papers by Caroline Series.
See, for instance, Non-
Euclidean geometry,
continued fractions, and
ergodic theory.

More recently, continued

fractions have come up in
studying the dynamics of
flows on translation
surfaces -- a special case of
which is studying billiards
in a rational polygon. For
example, continued
https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 8/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

fractions and Diophantine

approximations make an
appearance in studying
billiards in the wind-tree.
That is, imagine taking the
plane and placing identical
rectangular obstacles
centered at each integer
lattice point. Now consider
an ideal point-mass which
bounces between the
obstacles, reflecting off the
obstacles according to the
rule from geometric optics
that angle of incidence
equals angle of reflection.
Studying the motion of that
billiard (e.g., are there
periodic orbits, dense
orbits, escaping orbits,
recurrent orbits, etc.) can,
at least in some special
cases, boil down to studying
continued fractions. See
The Ehrenfest wind-tree
model: periodic directions,
recurrence, diffusion by
Hubert, Leliévre,
Troubetzkoy and Divergent
directions in some periodic
wind-tree models by
Delecroix.

Again, those probably aren't

the best ways to motivate
continued fractions if you're
seeing them for the first
time, but they do have
plenty of applications.

answered Apr 23 '14 at 23:28

cjohnson
631 4 10

There are many beautiful

theorems about continued
fractions. For example, a
real number is rational if
and only if its continued

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 9/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

fraction expansion is finite

(however, this is not the
case for decimal system,
since = 0.3 ⋯ is infinite
1

and rational). Also,

continued fraction is the
best possible rational
approximation to any given
irrational number. Hence it
can be used to approximate
irrationals (for example, π ).

For other applications, one

can use continued fraction
to solve the Pell's equation
or to generate a chaotic
process (by the Gaussian
map: x =
n+1
1
− ⌊
xn
⌋ ).
1

xn

You may want to read the

chapter in continued
fractions in Hardy &
Wright's book An
Introduction to the Theory
of Numbers. Or you can
also read a short article
titled Chaos in
Numberland: The secret life
of continued fractions by
John Barrow.

answered Apr 23 '14 at 6:06

Pan Yan
457 4 15

Two ideas which could be

useful for you:

1. Proposal: Combine
continued fractions with
the concepts of golden
ratio and fibonacci
numbers

I think starting with the

simplest continued fraction

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 10/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange
1
Φ = = [1, 1,
1
1 +
1
1+
1+⋯

offers charming
possibilities. With this
prototype you can bring
together continued
fractions with the golden
ratio and with the fibonacci
sequence as fundamental
and beautiful concepts.

Fibonacci Sequence and

continued fractions: Let
(F )
n the Fibonacci
n≥0

sequence, then

Fn
Φ = lim = [1, 1, 1, …
n→∞ F n−1

Golden ratio and

continued fractions:

–
√5 − 1
Φ = = [1, 1, 1, …
2

You could talk about the

mystic pentagram, detect
the golden ratio between
successive length and
diagonals of inscribed
pentagrams and reveal the
representation of Φ as
continued fraction. You
could also talk about golden
rectangles and their
applications by artists and
architects like Le Corbusier
and Dali or the classic
Parthenon with its many
geometric relations
resulting seemingly in
golden ratios.

I do appreciate the hint

from BIS HD. Phyllotaxis as
form of evolutionary
development which has

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 11/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

optimized the positions of

the seeds of sunflowers,
daisies or pine cones using
spirals is a great example
how simple and
fundamental concepts
[1, 1, 1, …] iteratively

applied are behind

seemingly complex
structures of nature. And,
counting the number of
seeds of successive spirals
will give you successive
Fibonacci numbers!

2. Proposal: Use
continued fractions and
lattice paths as
picturesque concept

I think, that lattice paths

are a fine, picturesque
example of an application of
continued fractions. Lattice
paths are structures we can
see and we can look what
happens, when they are
manipulated.

Here I would like to point to

a wonderful presentation of
continued fractions
summarizing the
contribution to this subject
of the great Flajolet and
also providing some
historical aspects. For me
this is a superb (and funny!)
example to familiarize the
audience with continued
fractions. At least the first
part of this presentation
could also be useful for your
needs. On page 149 you will
find a reference to a (rather
complex) real life
application in theoretical
physics Planar maps and
continued fractions from J.
Bouttier and E. Guitter.

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 12/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

Here is an article
Combinatorial aspects of
continued fractions from
Flajolet containing lattice
pathes and maybe you
could also find some
motivating material in the
survey Continued fractions
from Euclid to the present
day.

edited Apr 13 '17 at 12:19

Community ♦
1

answered Apr 26 '14 at 13:43

Markus Scheuer
57.8k 4 54 138

Application #1: The first

proof that e is irrational,
due to Euler, was based on
showing its continued
fraction expansion is
infinite:
e = [2, 1, 2, 1, 1, 4, 1, 1, 6, 1

with the obvious repeating

pattern of even numbers
separated by two 1's.

Application #2: A year

consists of 365.24219 days.
If we want to create a
calendar with a block of Y
years containing L leap
years, then Y years will
contain 365Y + L days.
The average number of days
in a year of each block is
(365Y + L)/Y = 365 + L/

, so we want L/Y to be a
good rational
approximation to .24219,
whose continued fraction
expansion is
[0, 4, 7, 1, 3, 24, 6, 2, 2]. The

first six continued fraction

convergents are 0, 1/4,

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 13/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

, ,
7/29 8/33 31/128 , and
752/3105 . The convergent
1/4 leads to the Julian

calendar having 1 leap year

every 4 years. The choice
L/Y = 8/33 is used in

Iran: 8 leap years in a block

of 33 years is part of the
Jalil calendar proposed by
Omar Khayyam in the year
1079. If we look at

intermediate convergents
between 31/128 and
752/3105 , which by

definition are fractions

(31a + 8)/(128a + 33) for

a = 1, 2, … , 23, then at

a = 6 we get 194/801 , and

801 is nearly 800 , a nice

round 8 centuries. So let's

modify this a little to
consider
194/800 = 97/400 : this is

the Gregorian calendar,

which has 97 leap years
every 400 years, that is a
leap year every 4th year
except for years divisible by
100 but not by 400 (a total

of 100 − 3 = 97 leap
years).

Application #3: As spin

wrote in a comment, being
able to make a good guess
for the value of a rational
number when you know
only some approximation
to it (even if the
approximation is itself
rational!) is a key part of
Shor's algorithm for
factoring integers on a
quantum computer.
Guessing rational numbers
from numerical
approximations is also
important in doing
computations related to
elliptic curves, as William
Stein explained to me: if an
https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 14/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

elliptic curve E is defined

over Q and you use
complex analysis to
compute a coefficient of a
Weierstrass equation for E,
or to compute L(E, 1)/Ω,
all you get is a decimal
estimate for a number that
is supposed to be rational
and you want to decide
what that rational number
ought to be (which might
then be rigorously proved
by other methods).
Typically the decimal
approximation of the
rational number may have
far fewer digits than the full
period length, so you can't
guess the fraction as simply
as you can if someone asks
you what fraction
.333333333 probably is

(namely 1/3).

Here is an example of how

continued fractions let you
guess rational numbers
from decimal expansions,
which I did as a trick at the
end of a talk I gave today on
continued fractions. I asked
a student in the audience to
compute a fraction as a
decimal on a calculator and
tell me what digits showed
up on the calculator, but
make sure there was no
obviously periodic part
shown by the calculator and
not to tell me the original
fraction and make sure to
write down the original
fraction for comparison
with my guess later. The
student gave me
.1391200951 . Using a

computer algebra package, I

converted .1391200951
into a continued fraction: it
is

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 15/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

[0, 7, 5, 3, 6, 1, 56891, 1, 103

. The 56891 is so huge

compared to what comes
before that my educated
guess for the student's
original fraction is
[0, 7, 5, 3, 6, 1], which is

117/841 . That indeed was

the number the student

wrote down earlier. The
audience was impressed.
The actual decimal period
of 117/841 is 812, so I was
able to figure out a fraction
having a repeating decimal
period length over 800
knowing only the first 10
digits of its decimal
expansion.

answered Jan 29 '15 at 3:16

KCd
16.4k 38 73

Musical notes follow a

geometric sequence, for
their frequency f relative
n

to a base frequency f : 0

12 – n
fn = f0 × (√2)

For example, an A note has

defined frequency 440 Hz,
so a note 5 chromatic steps
above it (D note) is
12 –5
f5 = 440√2 = 440 × 1.33

But a musician will often

want to play a notes that are
small ratios of each other
because it sounds better. So
what are the best rational
approximations for 2 ? 5/12

Look at the continued

fraction:

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 16/17
10/24/2018 elementary number theory - What are the applications of continued fractions? - Mathematics Stack Exchange

5/12
2 = [1; 2, 1, 73, . . . ] ≈ {

So we can see that the

musician is probably
playing a ratio. It was
4

obvious for this interval but

you can try other intervals.

edited Dec 1 '17 at 12:11

answered Apr 27 '14 at 6:50

DanielV
17.6k 4 27 52

https://math.stackexchange.com/questions/585675/what-are-the-applications-of-continued-fractions 17/17