continuedfractions.lib

continuedfractions.lib.continued_fraction_real(x: int | Fraction | float | str | Decimal, /) → Generator[int, None, None]

Generates a (finite) sequence of elements of a (simple) continued fraction of the given real number.

The result may not always be exact, but an approximation depending on whether the given number \(x\) has an exact binary floating point representation.

The simple continued fraction representation of \(x\) is a number of the form

\[a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}\]

where \(a_0 = [x]\) is the integer part of \(x\), and the \(a_1,a_2\ldots\) are the (non-negative) quotients obtained by a repeated application of Euclidean division to the fractional part \(x - [x]\), which is called the remainder.

If the last coefficient \(a_n = 1\) the sequence can be rewritten as \([a_0; a_1, a_2\ldots, a_{n - 1} + 1]\).

As Python float values, like all floating point implementations, are finite precision representations of real numbers, the resulting simple continued fraction of \(x\) generated by this function may be approximate, not exact, and also not necessarily unique.

For non-rational real numbers it is best to pass decimal.Decimal values, with the context precision set to the highest level possible.

The results for rational numbers are guaranteed to be exact however large the number, subject to memory and hardware limitations of the running environment.

Invalid values will generate an error in either the fractions.Fraction or decimal.Decimal classes - no errors are raised directly in the function itself.

Parameters:

xint, fractions.Fraction, float, str, decimal.Decimal

The real number to represent as a simple continued fraction.

Yields:

int

Elements of a simple continued fraction of the given real number.

Examples

A few examples are given below of how this function can be used.

>>> list(continued_fraction_real(5000))
[5000]
>>> list(continued_fraction_real(Fraction(7, 4)))
[1, 1, 3]
>>> list(continued_fraction_real(-5000.0))
[-5000]
>>> list(continued_fraction_real(2/5))
[0, 2, 2, 1801439850948198]
>>> list(continued_fraction_real('2/5'))
[0, 2, 2]
>>> list(continued_fraction_real('-1/3'))
[-1, 1, 2]
>>> list(continued_fraction_real(1/1j))
Traceback (most recent call last):
...
TypeError: conversion from complex to Decimal is not supported
>>> list(continued_fraction_real("not a numeric string"))
Traceback (most recent call last):
...
decimal.InvalidOperation: [<class 'decimal.ConversionSyntax'>]
>>> list(continued_fraction_real(-649/200))
[-4, 1, 3, 12, 3, 1, 234562480591, 2, 5, 2]
>>> list(continued_fraction_real('-649/200'))
[-4, 1, 3, 12, 4]
>>> list(continued_fraction_real('-649/-200'))
Traceback (most recent call last):
...
ValueError: Invalid literal for Fraction: '-649/-200'
>>> list(continued_fraction_real(Decimal('0.3333')))
[0, 3, 3333]

continuedfractions.lib.continued_fraction_rational(frac: Fraction, /) → Generator[int, None, None]

Implementation of the core continued fraction algorithm which generates the (ordered) sequence of coefficients of the (finite) simple continued fraction of the given rational number.

The resulting sequence of coefficients \(a_0,a_1,\ldots a_n\), defines the simple continued fraction:

\[a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots\cfrac{1}{a_{n - 1} + \cfrac{1}{a_n}}}}\]

which is also written more compactly as:

\[[a_0; a_1, a_2\ldots, a_n]\]

The order of the continued fraction is said to be \(n\). If the last coefficient \(a_n = 1\) the sequence can be rewritten as \([a_0; a_1, a_2\ldots, a_{n - 1} + 1]\), which is then unique for the given rational.

Negative rational numbers can also be represented in this way, provided we use the Euclidean division lemma.

Parameters:

fracfractions.Fraction

The rational number to represented as a simple continued fraction.

Yields:

int

Coefficients of the unique simple continued fraction of the given rational number.

Notes

Every rational number has a unique simple continued fraction \([a_0;a_1,a_2,\ldots, a_n]\), where \(a_n > 1\), and this function will always produce this unique represention for any given rational.

Examples

A few examples are given below of how this function can be used.

>>> for e in continued_fraction_rational(Fraction(649, 200)):
...     print(e)
...
3
4
12
4
>>> tuple(continued_fraction_rational(Fraction(415, 93)))
(4, 2, 6, 7)
>>> tuple(continued_fraction_rational(Fraction(-649, 200)))
(-4, 1, 3, 12, 4)
>>> tuple(continued_fraction_rational(Fraction(123235, 334505)))
(0, 2, 1, 2, 1, 1, 250, 1, 13)

continuedfractions.lib.convergent(k: int, *coeffs: int) → Fraction

Returns the \(k\)-th convergent of a (simple) continued fraction from a sequence of its coefficients.

Given a (simple) continued fraction \([a_0;a_1,a_2,\ldots]\) the \(k\)-th convergent is defined as:

\[C_k = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 \ddots \cfrac{1}{a_{k-1} + \cfrac{1}{a_k}}}}\]

The result is a fractions.Fraction instance.

The integer \(k\) is called the order of the convergent, and if \([a_0;a_1,a_2,\ldots]\) is finite of order \(n\) then it has exactly \(n + 1\) convergents \(C_0,C_1,C_2,\ldots,C_n\) where the \(k\)-th convergent \(C_k = \frac{p_k}{q_k}\) is given by the recurrence relation:

\[\begin{split}\begin{align} p_k &= a_kp_{k - 1} + p_{k - 2} \\ q_k &= a_kq_{k - 1} + q_{k - 2}, \hskip{3em} k \geq 3 \end{align}\end{split}\]

where \(p_0 = a_0\), \(q_0 = 1\), \(p_1 = p_1p_0 + 1\), and \(q_1 = p_1\).

This function is a faithful implementation of this algorithm.

A ValueError is raised if \(k\) is not an integer or is an integer greater than the number of coefficients, or if any of the coefficient are not integers.

Parameters:

kint

The order of the convergent. Must be a non-negative integer less than the number of coefficients.

*coeffsint

A variable-length sequence of integer coefficients of a continued fraction.

Returns:

fractions.Fraction

A rational fraction constructed from the given sequence of coefficients of a continued fraction, representing the \(k\)-order convergent of a (finite) simple continued fraction as given by a sequence of coefficients.

Raises:

ValueError

If \(k\) is not a non-negative integer less than the number of coefficients, or if any of the elements are not integers.

Examples

>>> convergent(0, 3, 4, 12, 4)
Fraction(3, 1)
>>> convergent(1, 3, 4, 12, 4)
Fraction(13, 4)
>>> convergent(2, 3, 4, 12, 4)
Fraction(159, 49)
>>> convergent(3, 3, 4, 12, 4)
Fraction(649, 200)
>>> convergent(3)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> convergent(-1, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> convergent(4, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.

continuedfractions.lib.convergents(*coeffs: int) → Generator[Fraction, None, None]

Generates an (ordered) sequence of all convergents of a (simple) continued fraction from a sequence of its coefficients.

If \(n\) is the order of the continued fraction represented by the given sequence of its coefficients then there are \(n + 1\) convergents \(C_0, C_1, \ldots, C_n\), and the function generates these in that order.

Parameters:

*elementsint

A variable-length sequence of integer coefficients of a (simple) continued fraction.

Yields:

fractions.Fraction

Each convergent that is generated is a fractions.Fraction instance and a \(k\)-th convergent of the given continued fraction.

Raises:

ValueError

If there are any non-integer coefficients, or the tail coefficients are not positive integers.

Examples

>>> tuple(convergents(3))
(Fraction(3, 1),)
>>> tuple(convergents(3, 2))
(Fraction(3, 1), Fraction(7, 2))
>>> tuple(convergents(3, 4, 12, 4))
(Fraction(3, 1), Fraction(13, 4), Fraction(159, 49), Fraction(649, 200))
>>> tuple(convergents(-5, 1, 1, 6, 7))
(Fraction(-5, 1), Fraction(-4, 1), Fraction(-9, 2), Fraction(-58, 13), Fraction(-415, 93))
>>> tuple(convergents(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
(Fraction(1, 1), Fraction(3, 2), Fraction(10, 7), Fraction(43, 30), Fraction(225, 157), Fraction(1393, 972), Fraction(9976, 6961), Fraction(81201, 56660), Fraction(740785, 516901), Fraction(7489051, 5225670))

continuedfractions.lib.fraction_from_coefficients(*coeffs: int) → Fraction

Returns the rational number represented by a (simple) continued fraction from a sequence of its coefficients.

The coefficient must be given as positional arguments: if your coefficients are contained in an iterable unpack them in the function call using the unpacking operator *, as described in the examples below.

Parameters:

*coeffsint

A variable-length sequence of integer coefficients of a simple continued fraction.

Returns:

fractions.Fraction

A rational number constructed from a sequence of coefficients of a simple continued fraction which represents the number.

Raises:

ValueError

If any of the coefficients are not integers, or the tail coefficients are not positive.

Examples

>>> fraction_from_coefficients(3, 4, 12, 4)
Fraction(649, 200)
>>> fraction_from_coefficients(-4, 1, 3, 12, 4)
Fraction(-649, 200)
>>> fraction_from_coefficients(4, 2, 6, 7)
Fraction(415, 93)
>>> fraction_from_coefficients(*[4, 2, 6, 7])
Fraction(415, 93)
>>> fraction_from_coefficients(4.5, 2, 6, 7)
Traceback (most recent call last):
...
ValueError: Continued fraction coefficients must be integers, and all coefficients from the 1st onwards must be positive.

continuedfractions.lib.left_mediant(r: Fraction, s: Fraction, /, *, dir: str = 'left', k: int = 1) → Fraction

Returns the \(k\)-th left- or right-mediant of two rational numbers.

For a positive integer \(k\), the \(k\)-th left-mediant of two rational numbers \(r = \frac{a}{b}\) and \(s = \frac{c}{d}\), where \(b, d, b + d \neq 0\), is defined as:

\[\frac{ka + c}{kb + d}, \hskip{3em} k \geq 1\]

while the \(k\)-th right mediant is defined as:

\[\frac{a + kc}{b + kd}, \hskip{3em} k \geq 1\]

If we assume that \(r < s\) and \(bd > 0\) then these mediants have the property that:

\[\frac{a}{b} < \frac{ka + c}{kb + d} \leq \frac{a + kc}{b + kd} < \frac{c}{d}, \hskip{3em} k \geq 1\]

where equality holds for \(k = 1\). If we let \(k \to \infty\) then the mediants converge to opposite limits:

\[\begin{split}\begin{align} \lim_{k \to \infty} \frac{ka + c}{kb + d} &= \frac{a}{b} \\ \lim_{k \to \infty} \frac{a + kc}{b + kd} &= \frac{c}{d} \end{align}\end{split}\]

For the left mediant use dir="left", while for the right use dir="right". The default is dir="right". For k = 1 the left and right mediants are identical to the simple mediant \(\frac{a + c}{b + d}\).

Parameters:

rfractions.Fraction

The first rational number.

sfractions.Fraction

The second rational number.

dirstr, default=’right’

The “direction” of the mediant - ‘left’ or ‘right’, as defined above.

kint, default=1

The order of the mediant, as defined above.

Returns:

fractions.Fraction

The k-th left- or right-mediant of the two given rational numbers.

Examples

>>> mediant(Fraction(1, 2), Fraction(3, 5))
Fraction(4, 7)
>>> mediant(Fraction(1, 2), Fraction(3, 5), dir='left')
Fraction(4, 7)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=2)
Fraction(7, 12)
>>> mediant(Fraction(1, 2), Fraction(3, 5), dir='left', k=2)
Fraction(5, 9)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=3, dir='right')
Fraction(10, 17)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=3, dir='left')
Fraction(6, 11)

continuedfractions.lib.mediant(r: Fraction, s: Fraction, /, *, dir: str = 'right', k: int = 1) → Fraction

Returns the \(k\)-th left- or right-mediant of two rational numbers.

For a positive integer \(k\), the \(k\)-th left-mediant of two rational numbers \(r = \frac{a}{b}\) and \(s = \frac{c}{d}\), where \(b, d, b + d \neq 0\), is defined as:

\[\frac{ka + c}{kb + d}, \hskip{3em} k \geq 1\]

while the \(k\)-th right mediant is defined as:

\[\frac{a + kc}{b + kd}, \hskip{3em} k \geq 1\]

If we assume that \(r < s\) and \(bd > 0\) then these mediants have the property that:

\[\frac{a}{b} < \frac{ka + c}{kb + d} \leq \frac{a + kc}{b + kd} < \frac{c}{d}, \hskip{3em} k \geq 1\]

where equality holds for \(k = 1\). If we let \(k \to \infty\) then the mediants converge to opposite limits:

\[\begin{split}\begin{align} \lim_{k \to \infty} \frac{ka + c}{kb + d} &= \frac{a}{b} \\ \lim_{k \to \infty} \frac{a + kc}{b + kd} &= \frac{c}{d} \end{align}\end{split}\]

For the left mediant use dir="left", while for the right use dir="right". The default is dir="right". For k = 1 the left and right mediants are identical to the simple mediant \(\frac{a + c}{b + d}\).

Parameters:

rfractions.Fraction

The first rational number.

sfractions.Fraction

The second rational number.

dirstr, default=’right’

The “direction” of the mediant - ‘left’ or ‘right’, as defined above.

kint, default=1

The order of the mediant, as defined above.

Returns:

fractions.Fraction

The k-th left- or right-mediant of the two given rational numbers.

Examples

>>> mediant(Fraction(1, 2), Fraction(3, 5))
Fraction(4, 7)
>>> mediant(Fraction(1, 2), Fraction(3, 5), dir='left')
Fraction(4, 7)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=2)
Fraction(7, 12)
>>> mediant(Fraction(1, 2), Fraction(3, 5), dir='left', k=2)
Fraction(5, 9)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=3, dir='right')
Fraction(10, 17)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=3, dir='left')
Fraction(6, 11)

continuedfractions.lib.remainder(k: int, *coeffs: int) → Fraction

Returns the \(k\)-th remainder of a (simple) continued fraction from a sequence of its coefficients.

Given a (simple) continued fraction \([a_0;a_1,a_2,\ldots]\) the \(k\)-th remainder \(R_k\) is the (simple) continued fraction \([a_k; a_{k + 1}, a_{k + 2}, \ldots]\):

\[R_k = a_k + \cfrac{1}{a_{k + 1} + \cfrac{1}{a_{k + 2} \ddots }}\]

where \(R_0\) is just the original continued fraction, i.e. \(R_0 = [a_0; a_1, a_2, \ldots]\).

The remainders have the property that:

\[R_{k - 1} = a_{k - 1} + \frac{1}{R_k}, \hskip{3em} k \geq 1\]

If the continued fraction \([a_0; a_1, a_2,\ldots]\) is finite of order \(n\) then all \(R_k\) are rational. If we let \(R_k = \frac{s_k}{t_k}\) then the property above can be written as:

\[R_{k - 1} = \frac{s_{k - 1}}{t_{k - 1}} = \frac{a_{k - 1}s_k + t_k}{s_k}, \hskip{3em} k \geq 1\]

As this library can only represent finite continued fractions, this function always produces remainders as instances of Fraction.

The integer \(k\) must be non-negative and cannot exceed the order of the continued fraction, i.e. the number of tail coefficients.

Parameters:

kint

The index of the remainder. Must be a non-negative integer not exceeding the order of the continued fraction.

*elementsint

A variable-length sequence of integer coefficients of a (simple) continued fraction.

Returns:

fractions.Fraction

A rational fraction constructed from the given sequence of coefficients of a continued fraction, representing its \(k\)-th remainder, as defined above.

Raises:

ValueError

If \(k\) is not an integer, or is an integer greater than the number of coefficients, or if any of the coefficients are not integers, or if the tail coefficients are not positive integers.

Examples

>>> remainder(0, 3, 4, 12, 4)
Fraction(649, 200)
>>> remainder(1, 3, 4, 12, 4)
Fraction(200, 49)
>>> remainder(2, 3, 4, 12, 4)
Fraction(49, 4)
>>> remainder(3, 3, 4, 12, 4)
Fraction(4, 1)
>>> remainder(0, -5, 1, 1, 6, 7)
Fraction(-415, 93)
>>> remainder(1, -5, 1, 1, 6, 7)
Fraction(93, 50)
>>> remainder(2, -5, 1, 1, 6, 7)
Fraction(50, 43)
>>> remainder(3, -5, 1, 1, 6, 7)
Fraction(43, 7)
>>> remainder(4, -5, 1, 1, 6, 7)
Fraction(7, 1)
>>> remainder(1)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(-1, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(4, 3, 4, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(1, 3, 0, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.
>>> remainder(1, 3, -1, 12, 4)
Traceback (most recent call last):
...
ValueError: `k` must be a non-negative integer not exceeding the order of the continued fraction (number of tail coefficients), and the tail coefficients must all be positive integers.

continuedfractions.lib.remainders(*coeffs: int) → Generator[Fraction, None, None]

Generates an (ordered) sequence of all remainders of a (simple) continued fraction from a sequence of its coefficients in descending order of index.

If \(n\) is the order of the continued fraction represented by the given sequence of its coefficients then there are \(n + 1\) remainders \(R_0, R_1, \ldots, R_n\), and the function generates these in reverse order \(R_0, R_1, \ldots, R_n\).

Parameters:

*elementsint

A variable-length sequence of integer coefficients of a (simple) continued fraction.

Yields:

fractions.Fraction

Each remainder generated is a fractions.Fraction instance and a \(k\)-th remainder of the given continued fraction.

Raises:

ValueError

If no coefficients are given, or there are any non-integer elements, or the tail coefficients are not positive integers.

Examples

>>> tuple(remainders(3))
(Fraction(3, 1),)
>>> tuple(remainders(3, 2))
(Fraction(2, 1), Fraction(7, 2))
>>> tuple(remainders(3, 4, 12, 4))
(Fraction(4, 1), Fraction(49, 4), Fraction(200, 49), Fraction(649, 200))
>>> tuple(remainders(-5, 1, 1, 6, 7))
(Fraction(7, 1), Fraction(43, 7), Fraction(50, 43), Fraction(93, 50), Fraction(-415, 93))
>>> tuple(remainders(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
(Fraction(10, 1), Fraction(91, 10), Fraction(738, 91), Fraction(5257, 738), Fraction(32280, 5257), Fraction(166657, 32280), Fraction(698908, 166657), Fraction(2263381, 698908), Fraction(5225670, 2263381), Fraction(7489051, 5225670))
>>> tuple(remainders())
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
>>> tuple(remainders(0, 0))
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
>>> tuple(remainders(1, 0))
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.
>>> tuple(remainders(1, 2, -1))
Traceback (most recent call last):
...
ValueError: Continued fraction elements must be integers, and all tail elements (from the 1st element onwards) must be positive.

continuedfractions.lib.right_mediant(r: Fraction, s: Fraction, /, *, dir: str = 'right', k: int = 1) → Fraction

Returns the \(k\)-th left- or right-mediant of two rational numbers.

For a positive integer \(k\), the \(k\)-th left-mediant of two rational numbers \(r = \frac{a}{b}\) and \(s = \frac{c}{d}\), where \(b, d, b + d \neq 0\), is defined as:

\[\frac{ka + c}{kb + d}, \hskip{3em} k \geq 1\]

while the \(k\)-th right mediant is defined as:

\[\frac{a + kc}{b + kd}, \hskip{3em} k \geq 1\]

If we assume that \(r < s\) and \(bd > 0\) then these mediants have the property that:

\[\frac{a}{b} < \frac{ka + c}{kb + d} \leq \frac{a + kc}{b + kd} < \frac{c}{d}, \hskip{3em} k \geq 1\]

where equality holds for \(k = 1\). If we let \(k \to \infty\) then the mediants converge to opposite limits:

\[\begin{split}\begin{align} \lim_{k \to \infty} \frac{ka + c}{kb + d} &= \frac{a}{b} \\ \lim_{k \to \infty} \frac{a + kc}{b + kd} &= \frac{c}{d} \end{align}\end{split}\]

For the left mediant use dir="left", while for the right use dir="right". The default is dir="right". For k = 1 the left and right mediants are identical to the simple mediant \(\frac{a + c}{b + d}\).

Parameters:

rfractions.Fraction

The first rational number.

sfractions.Fraction

The second rational number.

dirstr, default=’right’

The “direction” of the mediant - ‘left’ or ‘right’, as defined above.

kint, default=1

The order of the mediant, as defined above.

Returns:

fractions.Fraction

The k-th left- or right-mediant of the two given rational numbers.

Examples

>>> mediant(Fraction(1, 2), Fraction(3, 5))
Fraction(4, 7)
>>> mediant(Fraction(1, 2), Fraction(3, 5), dir='left')
Fraction(4, 7)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=2)
Fraction(7, 12)
>>> mediant(Fraction(1, 2), Fraction(3, 5), dir='left', k=2)
Fraction(5, 9)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=3, dir='right')
Fraction(10, 17)
>>> mediant(Fraction(1, 2), Fraction(3, 5), k=3, dir='left')
Fraction(6, 11)