Continued Fractions#
This library deals with (finite, simple) continued fractions, which are objects for representing rational numbers as “nested” fractions, for example, \(\frac{649}{200} = \frac{3 \times 200 + 49}{200} = 3.245\) which has the continued fraction:
This is derived by repeatedly applying Euclid’s division lemma:
The numbers \(3, 4, 12, 4\) are called coefficients of the continued fraction \([3; 4, 12, 4]\), and the number of coefficients after the first - in this case \(3\) - is defined to be its order. The order can be finite or infinite depending on whether the number represented is rational or irrational, as will be discussed later.
The representation \([3; 4, 12, 4]\) is called simple (or regular) because all of the numerators in the fractional terms are equal to \(1\), which makes the fractions irreducible (cannot be simplified further). Mathematically, the continued fraction is written as \([3; 4, 12, 4]\). The representation is also unique - the only other representation is \([3; 4, 12, 3, 1]\), which can be rewritten as \([3; 4, 12, 4]\).
Note
All references to “continued fraction” are to the simple forms.
The leading integer \(3\), which is the integer part of \(\frac{649}{200} = 3.245\), can be viewed as the “head” of the continued fraction, and the integers \(4, 12, 4\), which determine the fractional part \(\cfrac{1}{4 + \cfrac{1}{12 + \cfrac{1}{4}}} = \frac{49}{200} = 0.245\) of the continued fraction, as its “tail”. The order of the continued fraction is therefore the length of its tail.
The notation for continued fractions in the documentation is the widely used tuple notation \([a_0; a_1, a_2, \ldots, a_n, \ldots]\), where the \(a_i\) are integers, standing for the expression:
where \(a_0\) is the integer part, and \(a_1,a_2,\ldots\) are (positive) integers defining the fractional part, in the representation. If the order is finite, i.e. \(n < \infty\), then this expression describes a rational number. We can take the last coefficient \(a_n\) to be greater than \(1\) because \([a_0; a_1, a_2, \ldots a_{n - 1}, a_n = 1] = [a_0; a_1, a_2, \ldots a_{n - 1} + 1]\).
Creating Continued Fractions from Numeric Types#
Import the core class continuedfractions.continuedfraction.ContinuedFraction.
>>> from continuedfractions.continuedfraction import ContinuedFraction
The ContinuedFraction instance for \(\frac{649}{200}\) can be created as follows.
>>> cf = ContinuedFraction(649, 200)
>>> cf
ContinuedFraction(649, 200)
Note
The same instance can also be constructed using ContinuedFraction('649/200'), ContinuedFraction('3.245'), ContinuedFraction(Fraction(649, 200)), ContinuedFraction(Fraction(649), 200)), ContinuedFraction(649, Fraction(200))), and ContinuedFraction(Decimal('3.245')), and even ContinuedFraction(ContinuedFraction(649, 200)) .
But passing a numeric literal such as 649/200 will result in an evaluation of the decimal integer division using binary floating point division, thus producing a fractional approximation, in this case, ContinuedFraction(3653545197704315, 1125899906842624).
Note
All Python shell excerpts below (and elsewhere) were run in a Python 3.11.11 environment.
The coefficients of ContinuedFraction(649, 200) can be obtained via the coefficients property, which returns a generator of the coefficients. The order \(3\) can be obtained via the order property:
>>> cf = ContinuedFraction(649, 200)
>>> tuple(cf.coefficients)
(3, 4, 12, 4)
>>> cf.order
3
For more details on the coefficients and order properties see this.
The decimal.Decimal value of ContinuedFraction(649, 200) can be obtained the as_decimal() method.
>>> cf.as_decimal()
Decimal('3.245')
Decimal Precision#
According to the documentation the Python decimal library supports arbitrary precision arithmetic, subject to the limitations of the running environment, system, hardware etc. It does this via context objects for Decimal instances, in which the precision can be set to whatever is appropriate to the computation or experiment of interest, subject to the usual limitations.
An example is given below:
# Inspect the current context
>>> decimal.getcontext()
Context(prec=28, rounding=ROUND_HALF_EVEN, Emin=-999999, Emax=999999, capitals=1, clamp=0, flags=[Inexact, Rounded], traps=[InvalidOperation, DivisionByZero, Overflow])
>>> Decimal('1') / 3
Decimal('0.3333333333333333333333333333')
# Increase the precision to 100 digits, including the integer part of the number
>>> decimal.getcontext().prec = 100
>>> Decimal('1') / 3
Decimal('0.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333')
See the Decimal FAQ for more information and examples.
Irrational Numbers#
Rational numbers are represented by finite continued fractions, while irrational numbers can only be represented by infinite continued fractions. There are infinitely many rational and irrational numbers that cannot be represented exactly as binary fractions, which form the basis for floating point arithmetic, and, therefore, cannot be represented exactly by Python float instances, for example, \(\frac{1}{3} = 0.33333...\) which, as a float value 1/3 leads to the approximate Python fraction Fraction(6004799503160661, 18014398509481984).
It is possible to approximate irrationals using the from_coefficients() method. An example is given below for the irrational \(\sqrt{2}\), which is given by the infinite periodic continued fraction \([1; 2, 2, 2, \ldots]\), where the decimal.Decimal precision has been set to \(100\):
>>> sqrt2 = ContinuedFraction(math.sqrt(2))
>>> sqrt2
ContinuedFraction(6369051672525773, 4503599627370496)
>>> tuple(sqrt2.coefficients)
# -> (1, 2, 2, 2, 2, ... ,1, 1, 10, 2, ... ,1, 3, 1, 17, 12, 3, 2, 6, 1, 11, 2, 2)
>>> float(sqrt2)
1.4142135623730951
>>> sqrt2.as_decimal()
Decimal('1.4142135623730951454746218587388284504413604736328125')
>>> Decimal(math.sqrt(2)).as_integer_ratio()
Fraction(6369051672525773, 4503599627370496)
This approximation may be compared to the first one million digit representation of \(\sqrt{2}\).
Creating Continued Fractions From Coefficients#
Continued fractions can also be constructed from sequences of coefficients, using either the from_coefficients() class method, or the extend() or truncate() instance methods. Each is described below.
Sequences of Coefficients#
The from_coefficients() class method can be used to create new instances from a complete (ordered) sequence of coefficients. Some examples are given below.
>>> cf = ContinuedFraction.from_coefficients(3, 4, 12, 4)
>>> cf
ContinuedFraction(649, 200)
>>> cf_inverse = ContinuedFraction.from_coefficients(0, 3, 4, 12, 4)
>>> cf_inverse
ContinuedFraction(200, 649)
>>> cf_negative_inverse = ContinuedFraction.from_coefficients(-1, 1, 2, 4, 12, 4)
>>> cf_negative_inverse
ContinuedFraction(-200, 649)
>>> tuple(cf_negative_inverse.coefficients)
(-1, 1, 2, 4, 12, 4)
A ValueError is raised if the given coefficients are not integers, or if any of the tail coefficients are not positive integers.
>>> ContinuedFraction.from_coefficients('0', 1)
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.
In-place Extension#
The extend() instance method can be used to perform an in-place extension from new coefficients - the new coefficients are added to the existing instance tail in the given order. To be precise, given a continued fraction \([a_0; a_1, \ldots, a_n]\) of order \(n\) and an array of \(k \geq 1\) non-negative integers \((b_1, \ldots, b_k)\) the extend() method implements the mapping:
Some examples are given below.
>>> cf = ContinuedFraction.from_coefficients(3, 4, 12, 4)
>>> cf
ContinuedFraction(649, 200)
>>> id(cf)
4762928384
>>> cf.extend(5, 2)
>>> cf
ContinuedFraction(7457, 2298)
>>> tuple(cf.coefficients)
(3, 4, 12, 4, 5, 2)
>>> assert cf == ContinuedFraction.from_coefficients(3, 4, 12, 4, 5, 2)
# True
>>> id(cf)
4762928384
The result is an in-place modification of the existing instance, with the same object ID as before. All other attributes or properties will reflect the new values as determined by the complete sequence of coefficients formed by the original coefficients and the new coefficients provided with extend().
A ValueError is raised if the tail coefficients provided are invalid, e.g. not positive integers.
>>> cf = ContinuedFraction.from_coefficients(3, 4, 12, 4)
>>> cf
ContinuedFraction(649, 200)
>>> cf.extend(0, 4)
...
ValueError: The coefficients to be added to the tail must be positive integers.
>>> cf.extend(1, -1)
...
ValueError: The coefficients to be added to the tail must be positive integers.
Note
If the last of the new coefficients passed to extend() happens to be \(1\) then it is added to the previous coefficient to ensure uniqueness of the new sequence of coefficients of the resulting continued fraction, e.g.:
>>> cf = ContinuedFraction.from_coefficients(3, 4, 12, 3)
>>> cf
ContinuedFraction(490, 151)
>>> cf.extend(1)
>>> cf
ContinuedFraction(649, 200)
>>> tuple(cf.coefficients)
(3, 4, 12, 4)
In-place Truncation#
The truncate() instance method can be used to perform an in-place truncation of a contiguous trailing segment of the existing tail - the tail coefficients to be truncated are removed from the existing tail in the given order. To be precise, given a continued fraction \([a_0; a_1, \ldots, a_n]\) of order \(n\) and a \(k\)-length segment (or contiguous section) \((a_{n - k + 1}, \ldots, a_n)\) of its tail, where \(1 \leq k \leq n\), the extend() method implements the mapping:
Some examples are given below.
>>> cf = ContinuedFraction.from_coefficients(3, 4, 12, 4)
>>> cf
ContinuedFraction(649, 200)
>>> id(cf)
4921448896
>>> cf.truncate(12, 4)
>>> cf
ContinuedFraction(13, 4)
>>> tuple(cf.coefficients)
(3, 4)
>>> assert cf == ContinuedFraction.from_coefficients(3, 4)
# True
>>> id(cf)
4921448896
The result is an in-place modification of the existing instance, with the same object ID as before. All other attributes or properties will reflect the new values as determined by the complete sequence of coefficients formed by the truncation of the tail coefficients provided with truncate().
A ValueError is raised if the tail coefficients provided are invalid, e.g. not positive integers, or do not form a contiguous trailing segment of the existing tail.
>>> cf = ContinuedFraction.from_coefficients(3, 4, 12, 4)
>>> cf
ContinuedFraction(649, 200)
>>> cf.truncate(0, 4)
...
ValueError: The coefficients to be truncated from the tail must consist of positive integers and form a contiguous trailing segment of the tail.
>>> cf.truncate(3, 4, 12, 4)
...
ValueError: The coefficients to be truncated from the tail must consist of positive integers and form a contiguous trailing segment of the tail.
Rational Operations#
The ContinuedFraction class is a subclass of fractions.Fraction and supports all of the rational operations implemented in the superclass. This means that ContinuedFraction instances are fully operable as rational numbers
Rational operations can, in principle, involve any instance of numbers.Rational, but in practice correct, predictable results are only guaranteed with int, Fraction and of course ContinuedFraction, and in these cases the outputs are always new ContinuedFraction instances.
Binary operations involving incompatible types such as decimal.Decimal or complex will trigger errors.
>>> ContinuedFraction('1.5') + Decimal('0.5')
TypeError: argument should be a string or a Rational instance
>>> ContinuedFraction(3, 2) + complex(1, 2)
TypeError: argument should be a string or a Rational instance
The full set of rational operations, which are implemented by overriding certain magic methods, can be viewed directly in the class source.
“Negative” Continued Fractions#
A brief explanation is given here of how negation of ContinuedFraction objects has been implemented, using as an example the rational number \(\frac{-415}{93} = \frac{-5 \times 93 + 50}{93}\), which has the continued fraction \([-5; 1, 1, 6, 7]\):
in comparison with \(\frac{415}{93} = \frac{4 \times 93 + 43}{93}\), which has the continued fraction \([4; 2, 6, 7]\):
The implementation is again based on Euclid’s division lemma . Let \(\frac{a}{b}\) be a positive rational with \(a > b\) and \(a, b\) coprime, and \([a_0;a_1,\ldots,a_n]\) the simple continued fraction of order \(n \geq 1\) of \(\frac{a}{b}\), where we can assume \(a_n > 1\). The lemma implies that there are unique, positive integers \(q, v\), with \(0 < v < b\), such that \(a = qb + v\). Then:
where \(R_1 = [a_1; a_2, \ldots, a_n]\) is the “residual”, \((n - 1)\)-order simple continued fraction of \(\frac{b}{v}\), also called the 1st remainder of the continued fraction \([a_0;a_1,\ldots,a_n]\) of \(\frac{a}{b}\). If \(v = 1\) then \(R_1 = [b;]\) and \([q; b]\) is the simple continued fraction of \(\frac{a}{b}\). However, if \(v > 1\) then \(R_1\) is defined and and has the inversion \(\frac{1}{R_1} = [0; a_1, \ldots, a_n]\).
Wriring \(-a = -(qb + v)\) as:
we have:
where \(R_1 - 1 = [a_1 - 1;a_2,\ldots, a_n]\) and \(\frac{1}{R_1 - 1} = [0; a_1 - 1, a_2, a_3,\ldots, a_n]\).
Note
If the last coefficient \(a_n = 1\) then \([a_0; a_1, \ldots, a_n] = [a_0;a_1,\ldots,a_{n - 1} + 1]\) is of order \((n - 1)\). So in the representation \([-(q + 1); 1, a_1 - 1, a_2, a_3,\ldots, a_n]\) above for \(-\frac{a}{b}\), if \(a_1 = 2\) then \(a_1 - 1 = 1\) and the segment \([-(q + 1); 1, a_1 - 1] = [-(q + 1); 1, 1] = [-(q + 1); 2]\) is of order \(1\).
If \(\bar{R}_1\) denotes the 1st remainder \([1; a_1 - 1, a_2, a_3,\ldots, a_n]\) in the representation above for \(-\frac{a}{b}\) then \(\bar{R}_1\) is an \(n\)-order, simple continued fraction. A special case is when \(a_1 = 1\): in this case \(a_0 = -1\) and \(\bar{R}_1 = [a_2 + 1; a_3, \ldots, a_n]\) is an \((n - 2)\)-order simple continued fraction. Note that this special case also applies when \(0 < a < b\).
Thus, we can say that if \([a_0; a_1,\ldots, a_n]\) is the \(n\)-order simple continued fraction of a positive rational number \(\frac{a}{b}\) then the simple continued fraction of \(-\frac{a}{b}\) is given by:
This provides a direct way to compute the continued fraction of the negative of a positive rational number, without going through usual division algorithm, and is used in the implementation of negation.
Coefficients and Order#
The coefficients (or coefficients) of a (possibly infinite), simple continued fraction \([a_0;a_1,a_2\cdots]\) of a real number \(x\) include the head \(a_0 = [x]\), which is the integer part of \(x\), and the tail coefficients \(a_1,a_2,\cdots\) which occur in the denominators of the fractional terms. The coefficients property returns a generator of the coefficients, e.g. for ContinuedFraction(649, 200):
>>> cf = ContinuedFraction(649, 200)
>>> cf.coefficients
<generator object ContinuedFraction.coefficients at 0x108c4b100>
>>> tuple(cf.coefficients)
(3, 4, 12, 4)
Each access of the coefficients property will involve a rerun of the core division algorithm (as implemented in continuedfractions.lib.continued_fraction_rational()). Although this can end up being expensive in computations, depending on how you are using the coefficients array, the advantage is that manual changes to the numerator and/or denominator, which is supported by the fractions.Fraction class, will be immediately reflected in the coefficients that are generated.
>>> cf = ContinuedFraction(3, 2)
>>> tuple(cf.coefficients)
(1, 2)
>>> cf._numerator, cf._denominator = 5, 2
>>> cf
ContinuedFraction(5, 2)
>>> tuple(cf.coefficients)
(2, 2)
The order of a continued fraction is defined to be number of its tail coefficients, i.e. the coefficients defining the fractional part of the number represented by the continued fraction. Thus, for ContinuedFraction(649, 200) the order is 3:
>>> cf.order
1
All ContinuedFraction instances will have a finite sequence of coefficients and thus a finite order. The integers represent the special case of zero-order continued fractions.
>>> ContinuedFraction(3).order
0
The coefficients and orders of ContinuedFraction instances are well behaved with respect to all rational operations supported by fractions.Fraction:
>>> tuple(ContinuedFraction(415, 93).coefficients)
(4, 2, 6, 7)
>>> ContinuedFraction(649, 200) + ContinuedFraction(415, 93)
ContinuedFraction(143357, 18600)
>>> tuple((ContinuedFraction(649, 200) + ContinuedFraction(415, 93)).coefficients)
(7, 1, 2, 2, 2, 1, 1, 11, 1, 2, 12)
>>> (ContinuedFraction(649, 200) + ContinuedFraction(415, 93)).order
10
For convenience a counter property is also available to keep counts of coefficients:
>>> cf = ContinuedFraction(649, 200)
>>> cf.counter
Counter({4: 2, 3: 1, 12: 1})
The result is a collections.Counter object, where the counts are displayed in order of the most common coefficients to the least (via collections.Counter.most_common()).
The counter is effectively refreshed on each access, so that the effects of any operations that modify the underlying instance are immediately reflected.
>>> cf.extend(1, 2, 3)
>>> cf
ContinuedFraction(7603, 2343)
>>> cf.counter
Counter({3: 2, 4: 2, 12: 1, 1: 1, 2: 1})
>>> cf.truncate(1, 2, 3)
>>> cf
ContinuedFraction(649, 200)
>>> cf.counter
Counter({4: 2, 3: 1, 12: 1})
Convergents and Rational Approximations#
For an integer \(k \geq 0\) the \(k\)-th convergent \(C_k\) of a (simple) continued fraction \([a_0; a_1,\ldots]\) of a real number \(x\) is the rational number \(\frac{p_k}{q_k}\) with the simple continued fraction \([a_0; a_1,\ldots,a_k]\) formed from the first \(k + 1\) coefficients of the original:
For a finite continued fraction of order \(n\) there will be \(n + 1\) convergents \(C_0, C_1, \ldots, C_n\), and the \((n + 1)\)-st convergent \(C_n = x\). The ContinuedFraction class provides a convergent() instance method to compute the \(k\)-th convergent for \(k=0,1,\ldots,n\).
>>> cf = ContinuedFraction(649, 200)
>>> cf.convergent(0), cf.convergent(1), cf.convergent(2), cf.convergent(3)
(ContinuedFraction(3, 1), ContinuedFraction(13, 4), ContinuedFraction(159, 49), ContinuedFraction(649, 200))
Using the continued fraction \([3; 4, 12, 4]\) of \(\frac{649}{200}\) as an example, we can verify that these convergents are mathematically correct.
Note
The index of a convergent of a continued fraction may be different from its order as a continued fraction, e.g. for the rational \(-\frac{415}{93}\) which has the continued fraction \([-5; 1, 1, 6, 7]\), the \(1\)-st convergent is the integer \(-4\) with the continued fraction \([-5; 1] = [-4;]\) of order \(0\), and the \(2\)-nd convergent is the rational \(-\frac{9}{2}\) with the continued fraction \([-5; 1, 1] = [-5; 2]\) of order \(1\).
Fast Algorithms for Computing Convergents#
Convergents are useful for fast approximation algorithms. A key property in this regard is the recurrence relation between the convergents given by:
where \(p_0 = a_0\), \(q_0 = 1\), \(p_1 = p_1p_0 + 1\), and \(q_1 = p_1\). (This can be proved by induction.) This means that the \(k\)-th convergent can be computed from the \((k - 1)\)-st and \((k - 2)\)-nd convergents. This formula is faithfully implemented, iteratively, by the convergent() method.
The same formula is also involved in the implementation of the convergents property, which returns a generator of an enumerated sequence of all the convergents of the continued fraction:
>>> cf = ContinuedFraction(649, 200)
>>> cf_convergents = dict(cf.convergents)
>>> cf_convergents
{0: ContinuedFraction(3, 1), 1: ContinuedFraction(13, 4), 2: ContinuedFraction(159, 49), 3: ContinuedFraction(649, 200)}
The result is an enumerated sequence of ContinuedFraction instances, where the enumeration is by convergent index.
The difference between consecutive convergents is given by the formula:
and this can be illustrated with the convergents of the continued fraction \([-5; 1, 1, 6, 7]\) of \(-\frac{415}{93}\):
>>> cf = ContinuedFraction(-415, 93)
>>> cf_convergents = dict(cf.convergents)
>>> cf_convergents
{0: ContinuedFraction(-5, 1), 1: ContinuedFraction(-4, 1), 2: ContinuedFraction(-9, 2), 3: ContinuedFraction(-58, 13), 4: ContinuedFraction(-415, 93)}
>>> cf_convergents[1] - cf_convergents[0]
ContinuedFraction(1, 1)
>>> cf_convergents[2] - cf_convergents[1]
ContinuedFraction(-1, 2)
>>> cf_convergents[3] - cf_convergents[2]
ContinuedFraction(1, 26)
>>> cf_convergents[4] - cf_convergents[3]
ContinuedFraction(-1, 1209)
Rational Approximation#
Convergents are useful for best rational approximations of real numbers: a rational number \(\frac{p}{q}\), where \(q > 0\), is said to be a best rational approximation of a real number \(x\), if \(\frac{p}{q}\) is closer to \(x\), as measured by \(\lvert \frac{p}{q} - x \rvert\), than any other rational number \(\frac{p\prime}{q\prime}\) (\(q\prime > 0\)) with denominator \(q\prime \leq q\).
Convergents have this property: this can be illustrated with a little example using the rational number \(-\frac{415}{93}\), which has the continued fraction \([-5; 1, 1, 6, 7]\), and its 3rd convergent \(-\frac{58}{13}\), which has the continued fraction \([-5; 1, 1, 6]\).
>>> cf = ContinuedFraction(-415, 93)
>>> cf.convergent(3)
ContinuedFraction(-58, 13)
# ``Decimal`` precision set to 28 digits (default)
>>> cf.convergent(3).as_decimal()
Decimal('-4.461538461538461538461538462')
>>> abs(cf - cf.convergent(3))
ContinuedFraction(1, 1209)
>>> abs(cf - cf.convergent(3)).as_decimal()
Decimal('0.0008271298593879239040529363110')
>>> abs(cf - ContinuedFraction(-58, 12))
ContinuedFraction(23, 62)
>>> abs(cf - ContinuedFraction(-58, 12)).as_decimal()
Decimal('0.3709677419354838709677419355')
Convergents have a stronger version of this property: namely a rational number \(\frac{p}{q}\) is a convergent of a (simple) continued fraction \([a_0; a_1, \ldots]\) of a real number \(x\) if and only if it is a best rational approximation of \(x\) compared to any other rational \(\frac{p\prime}{q\prime}\) (\(q\prime > 0\)) with denominator \(q\prime \leq q\). The sequence of convergents \((C_k)\) converges to \(x\) as \(k \to \infty\) - this is expressed formally by:
A simple example of convergent approximations of real numbers is \(\sqrt{2}\), which has the the continued fraction:
written more compactly as \([1; \bar{2}]\), where \(\bar{2}\) represents the infinite (periodic) sequence \(2, 2, 2, \ldots\). The convergents of \(\sqrt{2}\) can be constructed using the from_coefficients() method:
# 1st convergent of sqrt(2)
>>> ContinuedFraction.from_coefficients(1, 2)
ContinuedFraction(3, 2)
>>> ContinuedFraction.from_coefficients(1, 2).as_decimal()
>>> Decimal('1.5')
# 2nd convergent of sqrt(2)
>>> ContinuedFraction.from_coefficients(1, 2, 2)
ContinuedFraction(7, 5)
>>> ContinuedFraction.from_coefficients(1, 2, 2).as_decimal()
>>> Decimal('1.4')
# 3rd convergent of sqrt(2)
>>> ContinuedFraction.from_coefficients(1, 2, 2, 2)
ContinuedFraction(17, 12)
>>> ContinuedFraction.from_coefficients(1, 2, 2, 2).as_decimal()
>>> Decimal('1.416666666666666666666666667')
...
# 10th convergent of sqrt(2)
>>> ContinuedFraction.from_coefficients(1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)
ContinuedFraction(8119, 5741)
>>> ContinuedFraction.from_coefficients(1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2).as_decimal()
>>> Decimal('1.414213551646054694304128201')
The 10th convergent \(\frac{8119}{5741}\) of \(\sqrt{2}\) is accurate to \(6\) decimal places in the fractional part. The 100th convergent (with \(101\) coefficients consisting of the integer part \(1\), plus a tail of one hundred 2s), produces a closer approximation:
# Create a `ContinuedFraction` from the sequence 1, 2, 2, 2, ..., 2, with one hundred 2s in the tail
>>> sqrt2_100 = ContinuedFraction.from_coefficients(1, *[2] * 100)
ContinuedFraction(228725309250740208744750893347264645481, 161733217200188571081311986634082331709)
>>> tuple(sqrt2_100.coefficients)
# -> (1, 2, 2, 2, ..., 2) where there are `100` 2s after the `1`
>>> sqrt2_100.as_decimal()
Decimal('1.414213562373095048801688724')
The decimal value of ContinuedFraction.from_coefficients(1, *[2] * 100) in this construction is now accurate up to 27 digits in the fractional part, but the decimal representation stops there. This is because the decimal library uses a default contextual precision of 28 digits, including the integer part. The decimal precision can be increased, and the accuracy of the “longer” approximation above can be compared, as follows:
# `decimal.Decimal.getcontext().prec` stores the current context precision
>>> import decimal
>>> decimal.getcontext().prec
28
# Increase it to 100 digits, and try again
>>> decimal.getcontext().prec = 100
>>> sqrt2_100 = ContinuedFraction.from_coefficients(1, *[2] * 100)
>>> sqrt2_100
ContinuedFraction(228725309250740208744750893347264645481, 161733217200188571081311986634082331709)
>>> sqrt2_100.as_decimal()
Decimal('1.414213562373095048801688724209698078569671875376948073176679737990732478462093522589829309077750929')
Now, the decimal value of ContinuedFraction.from_coefficients(1, *[2] * 100) is accurate up to 75 digits in the fractional part, but deviates from the true value after the 76th digit onwards.
Even- and Odd-order Convergents#
The even- and odd-order convergents behave differently: the even-order convergents \(C_0,C_2,C_4,\ldots\) strictly increase from below \(x\), while the odd-order convergents \(C_1,C_3,C_5,\ldots\) strictly decrease from above \(x\), both at a decreasing rate. This is captured by the formula:
The ContinuedFraction class provides properties for generating even-order convergents (even_order_convergents) and odd-order convergents (odd_convergents), as illustrated below.
>>> dict(ContinuedFraction(649, 200).even_order_convergents)
{0: ContinuedFraction(3, 1), 2: ContinuedFraction(159, 49)}
>>> dict(ContinuedFraction(649, 200).odd_order_convergents)
{1: ContinuedFraction(13, 4), 3: ContinuedFraction(649, 200)}
As with the convergents property the result is a generator of enumerated sequence of ContinuedFraction instances, where the enumeration is by convergent index.
The different behaviour of even- and odd-order convergents can be illustrated by a ContinuedFraction approximation of \(\sqrt{2}\) with one hundred 2s in the tail, using dictionaries to store the even- and odd-order convergents:
# Increase the current context precision to 100 digits
>>> decimal.getcontext().prec = 100
#
# Construct an approximation for the square root of 2, with one hundred 2s in the tail
>>> cf = ContinuedFraction.from_coefficients(1, *([2] * 100))
>>> cf
>>> ContinuedFraction(228725309250740208744750893347264645481, 161733217200188571081311986634082331709)
>>> cf.as_decimal()
Decimal('1.414213562373095048801688724209698078569671875376948073176679737990732478462093522589829309077750929')
#
# Differences between consecutive even-order convergents
>>> cf_even_convergents = dict(cf.even_order_convergents)
>>> cf_even_convergents[2] - cf_even_convergents[0]
>>> ContinuedFraction(2, 5)
>>> cf_even_convergents[4] - cf_even_convergents[2]
>>> ContinuedFraction(2, 145)
>>> cf_even_convergents[6] - cf_even_convergents[4]
>>> ContinuedFraction(2, 4901)
>>> cf_even_convergents[8] - cf_even_convergents[6]
>>> ContinuedFraction(2, 166465)
>>> cf_even_convergents[10] - cf_even_convergents[8]
>>> ContinuedFraction(2, 5654885)
#
# Differences between consecutive odd-order convergents
>>> cf_odd_convergents = dict(cf.odd_order_convergents)
>>> cf_odd_convergents[3] - cf_odd_convergents[1]
>>> ContinuedFraction(-1, 12)
>>> cf_odd_convergents[5] - cf_odd_convergents[3]
>>> ContinuedFraction(-1, 420)
>>> cf_odd_convergents[7] - cf_odd_convergents[5]
>>> ContinuedFraction(-1, 14280)
>>> cf_odd_convergents[9] - cf_odd_convergents[7]
>>> ContinuedFraction(-1, 485112)
Semiconvergents#
Semiconvergents are mediants of consecutive convergents of continued fractions. More precisely, if \(\frac{p_{k - 1}}{ q_{k - 1}}\) and \(\frac{p_k}{q_k}\) are consecutive convergents of a (possibly infinite) continued fraction \([a_0;a_1,a_2,\ldots,a_k, a_{k + 1}, \ldots]\), and \(m\) is any positive integer, then the fraction:
is called a semiconvergent of \(\frac{p_{k - 1}}{q_{k - 1}}\) and \(\frac{p_k}{q_k}\). This is also the \(m\)-th right-mediant of the two (consecutive) convergents, and is an intermediate fraction between them (the mediant property). So, assuming that \(\frac{p_{k - 1}}{q_{k - 1}} \leq \frac{p_k}{q_k}\), for any positive integer \(m\), we have:
If on the other hand \(\frac{p_{k - 1}}{q_{k - 1}} \geq \frac{p_k}{q_k}\) the inequality above would be reversed.
In the definition given above of the \(m\)-th semiconvergent, the integer \(m\) is required to be in the range \(0..a_{k + 1}\), i.e. \(0 \leq m \leq a_{k + 1}\), where the corner cases are \(m = 0\) in which case the semiconvergent is equal to \(\frac{p_{k - 1}}{q_{k - 1}}\), and \(m = a_{n + 1}\) (if this is defined) in which the case the semiconvergent is equal to \(\frac{p_{k + 1}}{q_{k + 1}}\).
This definitin has been implemented as the semiconvergent() method. This takes two arguments: (1) a positive integer \(k\) determining two consecutive convergents \(\frac{p_{k - 1}}{q_{k - 1}}, \frac{p_k}{q_k}\) for which to take a semiconvergent, and (2) a positive integer \(m\) for the index of the semiconvergent (see the definition of “right-mediant”).
A few examples are given below for the continued fraction \([-5; 1, 1, 6, 7]\) for \(-\frac{415}{93}\).
>>> cf = ContinuedFraction(-415, 93)
>>> tuple(cf.coefficients)
(-5, 1, 1, 6, 7)
>>> dict(cf.convergents)
{0: ContinuedFraction(-5, 1), 1: ContinuedFraction(-4, 1), 2: ContinuedFraction(-9, 2), 3: ContinuedFraction(-58, 13), 4: ContinuedFraction(-415, 93)}
>>> cf.semiconvergent(3, 1)
ContinuedFraction(-67, 15)
>>> cf.semiconvergent(3, 2)
ContinuedFraction(-125, 28)
>>> cf.semiconvergent(3, 3)
ContinuedFraction(-183, 41)
>>> cf.semiconvergent(3, 4)
ContinuedFraction(-241, 54)
>>> cf.semiconvergent(3, 5)
ContinuedFraction(-299, 67)
>>> cf.semiconvergent(3, 6)
ContinuedFraction(-357, 80)
>>> cf.semiconvergent(3, 7)
ContinuedFraction(-415, 93)
Note
The continued fraction of an integer is of zero order, and thus has only one convergent - itself - and no semiconvergents. Attempting to call semiconvergent() on any integer-valued ContinuedFraction instance, for any value of \(k\) and \(m\), produces a ValueError.
>>> ContinuedFraction(1).semiconvergent(0, 1)
...
ValueError: `k` and `m` must be positive integers and `k` must be an integer in the range `1..n` where `n` is the order of the continued fraction
In relation to consecutive convergents \(\frac{p_{k - 1}}{q_{k - 1}}\) and \(\frac{p_k}{q_k}\) the \(m\)-th semiconvergent \(\frac{p_{k - 1} + mp_k}{q_{k - 1} + mq_k}\) is the mediant of their \((m - 1)\)-st semiconvergent \(\frac{p_{k - 1} + (m - 1)p_k}{q_{k - 1} + (m - 1)q_k}\) and the \(k\)-th convergent \(\frac{p_k}{q_k}\). The semiconvergent sequence \(\left( \frac{p_{k - 1} + mp_k}{q_{k - 1} + mq_k} \right)\) is monotonic in \(m\), bounded on one side by \(\frac{p_k}{q_k}\) (the side depends on whether \(k\) is odd or even), and has the limit \(\frac{p_k}{q_k}\) as \(m \to \infty\). This can be seen in the example above.
The semiconvergents also alternate in \(k\): the difference between the \(m\)-th semiconvergent \(\frac{p_{k - 1} + mp_k}{q_{k - 1} + mq_k}\) and the \((m - 1)\)-st semiconvergent \(\frac{p_{k - 1} + (m - 1)p_k}{q_{k - 1} + (m - 1)q_k}\) is given by:
This can be illustrated again using the continued fraction for \(-\frac{415}{93}\):
>>> cf = ContinuedFraction(-415, 93)
>>> tuple(cf.coefficients)
(-5, 1, 1, 6, 7)
>>> dict(cf.convergents)
{0: ContinuedFraction(-5, 1), 1: ContinuedFraction(-4, 1), 2: ContinuedFraction(-9, 2), 3: ContinuedFraction(-58, 13), 4: ContinuedFraction(-415, 93)}
>>> cf.semiconvergent(1, 1), cf.semiconvergent(1, 2)
(ContinuedFraction(-9, 2), ContinuedFraction(-13, 3))
>>> cf.semiconvergent(1, 2) - cf.semiconvergent(1, 1)
ContinuedFraction(1, 6)
>>> cf.semiconvergent(2, 1), cf.semiconvergent(2, 2)
(ContinuedFraction(-13, 3), ContinuedFraction(-22, 5))
>>> cf.semiconvergent(2, 2) - cf.semiconvergent(2, 1)
ContinuedFraction(-1, 15)
>>> cf.semiconvergent(3, 1), cf.semiconvergent(3, 2)
(ContinuedFraction(-67, 15), ContinuedFraction(-125, 28))
>>> cf.semiconvergent(3, 2) - cf.semiconvergent(3, 1)
ContinuedFraction(1, 420)
>>> cf.semiconvergent(4, 1), cf.semiconvergent(4, 2)
(ContinuedFraction(-473, 106), ContinuedFraction(-888, 199))
>>> cf.semiconvergent(4, 2) - cf.semiconvergent(4, 1)
ContinuedFraction(-1, 21094)
Note
When calling semiconvergent() the value of \(k\), which determines two consecutive convergents \(\frac{p_{k - 1}}{q_{k - 1}}, \frac{p_k}{q_k}\) of a continued fraction, cannot exceed the order of the continued fraction.
Remainders#
The \(k\)-th remainder \(R_k\) of a (simple) continued fraction \([a_0; a_1,\ldots]\) of a real number \(x\) is the (simple) continued fraction \([a_k;a_{k + 1},\ldots]\), obtained from the original by “removing” the coefficients of the \((k - 1)\)-st convergent \(C_{k - 1} := [a_0;a_1,\ldots,a_{k - 1}]\):
where \(R_0 = x\). As with convergents, we can also use \(R_k\) to denote the number represented by the associated continued fraction \([a_k;a_{k + 1},\ldots]\), and this number is rational if and only if the continued fraction is of finite order.
If \([a_0; a_1,\ldots]\) is of finite order \(n\) then \(R_k\) is of order \((n - k)\). The remainders of ContinuedFraction instances can be obtained via the remainder() method, which takes a non-negative integer not exceeding the order of the original.
>>> cf = ContinuedFraction(649, 200)
>>> cf.remainder(0), cf.remainder(1), cf.remainder(2), cf.remainder(3)
(ContinuedFraction(649, 200), ContinuedFraction(200, 49), ContinuedFraction(49, 4), ContinuedFraction(4, 1))
It is also possible to get all of the remainders at once using the remainders property, which returns a generator of an enumerated sequence of the remainders in descending order of index:
>>> dict(ContinuedFraction('3.245').remainders)
{3: ContinuedFraction(4, 1), 2: ContinuedFraction(49, 4), 1: ContinuedFraction(200, 49), 0: ContinuedFraction(649, 200)}
Using the simple continued fraction of \(\frac{649}{200}\) we can verify that these remainders are mathematically correct.
Given a (possibly infinite) continued fraction \([a_0; a_1, a_2,\ldots]\) the remainders \(R_0,R_1,\ldots\) have the property that:
where \(\frac{1}{R_k}\) denotes the inverted continued fraction \([0; a_k, a_{k + 1},\ldots]\). If the continued fraction \([a_0; a_1, a_2,\ldots]\) is finite of order \(n\) and we let \(R_k = \frac{s_k}{t_k}\) then:
This allows successive remainders to computed starting from \(R_n = [a_n;]\) and working backwards to \(R_0 = [a_0; a_1, \ldots, a_n]\), as implemented in the remainders library function remainders(), which is then called by the ContinuedFraction remainders property.
Khinchin Mean & Khinchin’s Constant#
For a (possibly infinite) continued fraction \([a_0; a_1, a_2,\ldots]\) and a positive integer \(n\) we define its \(n\)-th Khinchin mean \(K_n\) as the geometric mean of its first \(n\) coefficients starting from \(a_1\) (excluding the leading coefficient \(a_0\)):
So \(K_n\) is simply the geometric mean of the integers \(a_1, a_2,\ldots,a_n\), for \(n \geq 1\).
It has been proved that for irrational numbers, which have infinite continued fractions, there are infinitely many for which the quantity \(K_n\) approaches a constant \(K_0 \approx 2.685452\ldots\), called Khinchin’s constant, independent of the number. So:
The ContinuedFraction class provides a way of examining the behaviour of \(K_n\) via the khinchin_mean property, as indicated in the examples below.
>>> tuple(ContinuedFraction(649, 200).coefficients)
(3, 4, 12, 4)
>>> ContinuedFraction(649, 200).khinchin_mean
Decimal('5.76899828122963409526846589869819581508636474609375')
>>> tuple(ContinuedFraction(415, 93).coefficients)
(4, 2, 6, 7)
>>> ContinuedFraction(415, 93).khinchin_mean
Decimal('4.37951913988788898990378584130667150020599365234375')
>>> tuple((ContinuedFraction(649, 200) + ContinuedFraction(415, 93)).coefficients)
(7, 1, 2, 2, 2, 1, 1, 11, 1, 2, 12)
>>> (ContinuedFraction(649, 200) + ContinuedFraction(415, 93)).khinchin_mean
Decimal('2.15015313349074244086978069390170276165008544921875')
>>> ContinuedFraction(5000).khinchin_mean
For rational numbers, which have finite continued fractions, the Khinchin means are not defined for all \(n\), so this property is not all that useful for rationals. However, for approximations of irrationals the property is useful as given in the examples below using continued fraction approximations for \(\pi = [3; 7, 15, 1, 292, \ldots]\).
# 4th Khinchin mean for `\pi` using a continued fraction with `5` coefficients
>>> ContinuedFraction.from_coefficients(3, 7, 15, 1, 292).khinchin_mean
Decimal('13.2325345812843568893413248588331043720245361328125')
# 19th Khinchin mean for `\pi` using a continued fraction with `20` coefficients
>>> ContinuedFraction.from_coefficients(3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2).khinchin_mean
Decimal('2.60994679070748158977721686824224889278411865234375')
and \(\gamma = [0; 1, 1, 2, 1,\ldots]\), the Euler-Mascheroni constant:
# 4th Khinchin mean for `\gamma` using a continued fraction with `5` coefficients
>>> ContinuedFraction.from_coefficients(0, 1, 1, 2, 1).khinchin_mean
Decimal('1.4422495703074085238171164746745489537715911865234375')
# 19th Khinchin mean for `\gamma` using a continued fraction with `20` coefficients
>>> ContinuedFraction.from_coefficients(0, 1, 1, 2, 1, 2, 1, 4, 3, 13, 5, 1, 1, 8, 1, 2, 4, 1, 1, 40).khinchin_mean
Decimal('2.308255739839563336346373034757561981678009033203125')
The constant \(\gamma\), which has not been proved to be irrational, is defined as:
where \(H_n = \sum_{k=1}^n \frac1{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots \frac{1}{n}\) is the \(n\)-th harmonic number.
Height Functions#
Analogous to rational points in the plane the rationals \(\mathbb{Q}\) can be identified with elements of a subset of projective space \(\mathbb{P}^1(\mathbb{Q}) = \frac{\mathbb{Q}^2 \setminus \{(0, 0)\}}{\sim}\) consisting of equivalence classes \(\left[\frac{a}{c}:1\right]\), where \(\frac{a}{c} \in \mathbb{Q}\) and \(\sim\) is the (non-zero) scalar multiple equivalence relation. For a given rational \(P = \frac{a}{c}\) each equivalence class \(\left[\frac{a}{c}:1\right]\) is a collection of homogeneous coordinates for \(P\) in \(\mathbb{P}^1(\mathbb{Q})\), which are all non-zero scalar multiples of each other. We can choose as a representative projective point for \(P\) the class \(\left[a: c\right]\) where \(a, c \in \mathbb{Z}\) are not both zero.
In this setting, the (projective) height \(H(P)\) of \(P = \frac{a}{c}\) is defined as \(\text{max}(|a|, |c|)\), and the logarithmic height of \(P\) is defined as \(\text{log}\left(H(P)\right) = \text{log}\left(\text{max}(|a|, |c|)\right)\).
These are implemented by the height and log_height properties respectively.
Some examples are given below.
>>> ContinuedFraction(0, 1).height
1
>>> ContinuedFraction(2, 3).height
3
>>> ContinuedFraction(3, -2).height
3
>>> ContinuedFraction(0, 1).log_height
Decimal('0')
>>> ContinuedFraction(2, 3).log_height
Decimal('1.0986122886681097821082175869378261268138885498046875')
>>> ContinuedFraction(3, -2).log_height
Decimal('1.0986122886681097821082175869378261268138885498046875')
References#
[1] Baker, A. A. (2002). A concise introduction to the theory of numbers. Cambridge University Press.
[2] Barrow, J. D. (2000, June 1). Chaos in Numberland: The secret life of continued fractions. Plus.Maths.org. Retrieved February 19, 2024, from https://plus.maths.org/content/chaos-numberland-secret-life-continued-fractions
[3] Hatcher, A. (2024, September). Topology of Numbers. American Mathematical Society. https://pi.math.cornell.edu/~hatcher/TN/TNbook.pdf
[4] Python Software Foundation (n.d.). Decimal - Decimal fixed point and floating point arithmetic. Python 3.12.3 Documentation. Retrieved February 21, 2024, from https://docs.python.org/3/library/decimal.html
[5] Python Software Foundation (n.d.). Floating Point Arithmetic: Issues and Limitations. Python 3.12.3 Documentation. Retrieved February 20, 2024, from https://docs.python.org/3/tutorial/floatingpoint.html
[6] Python Software Foundation (n.d.). Fractions - Rational numbers. Python 3.12.3 Documentation. Retrieved February 21, 2024, from https://docs.python.org/3/library/fractions.html
[7] Khinchin, A. Y. (1997). Continued Fractions. Dover Publications.
[8] Nemiroff, R. J. (n.d.). The Square Root of Two to 1 Million Digits. Astronomy Picture of the Day. Retrieved March 13, 2024, from https://apod.nasa.gov/htmltest/gifcity/sqrt2.1mil