continuedfractions.sequences

continuedfractions.sequences.rationals(enumeration: Literal['cantor diagonal', 'cantor diagonal transposed', 'rectilinear', 'rectilinear transposed'], positive_only: bool = True) → Generator[ContinuedFraction, None, None]

typing.Generator : An enumerator of rational numbers \(\mathbb{Q}\) using an enumeration on Cantor’s 2D representation of the rationals.

By default it generates sequences of all positive rational numbers as ContinuedFraction objects with the user-specified enumeration on Cantor’s 2D representation of the rationals.

To include negative rationals and \(0\) set positive_only to False, as described in the documentation and the docstring examples below.

The enumeration type should be given by the enumeration argument, which should be one of the following:

• "cantor diagonal": for the standard way of enumerating rational

numbers using Cantor diagonalisation (with positive_only=False):

\[\frac{1}{1}, \frac{2}{1}, \frac{1}{2}, \frac{1}{3}, \frac{3}{1}, \frac{4}{1}, \frac{3}{2}, \frac{2}{3}, \frac{1}{4}, \ldots\]

• "cantor diagonal transposed": similar to the standard Cantor

diagonalisation (with positive_only=False), except the enumeration proceeds:

right 1 step ->
diagonal down 1 step ->
down 1 step ->
diagonal up 2 steps ->
...

and produces the sequence:

\[\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \ldots\]

• "rectilinear": an enumeration which proceeds in a reverse L-shaped

way (with positive_only=False):

down 1 step  ->
right 1 step -> up 1 step   -> right 1 step ->
down 2 steps -> left 2 steps -> down 1 step ->
right 3 steps -> up 3 steps -> right 1 step ->
down 4 steps  -> left 4 steps -> down 1 step ->
...

and produces the sequence:

\[\frac{1}{1}, \frac{2}{1}, \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{2}, \frac{3}{1}, \frac{4}{1}, \ldots\]

• "rectilinear transposed": an enumeration similar to "rectilinear"

(with positive_only=False) except the enumeration proceeds:

right 1 step  ->
down 1 step -> left 1 step   -> down 1 step ->
right 2 steps -> up 2 steps -> right 1 step ->
down 3 steps -> left 3 steps -> down 1 step ->
right 4 steps  -> up 4 steps -> right 1 step ->
...

and produces the sequence:

\[\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{3}{2}, \frac{2}{3}, \frac{1}{3}, \frac{1}{4}, \ldots\]

Parameters:

enumerationstr

A string literal which describes how the rationals should be enumerated:

• "cantor diagonal"

• "cantor diagonal transposed"

• "rectilinear"

• "rectilinear transposed"

positive_onlybool, default=True

Whether to generate only the positive rationals, which is true by default.

Yields:

ContinuedFraction

The rational numbers are generated as ContinuedFraction objects.

Raises:

ValueError

If enumeration is not an unrecognised or unsupported enumeration.

Examples

>>> rats = rationals(enumeration="cantor diagonal")
>>> first_ten = [next(rats) for _ in range(10)]
>>> first_ten
[ContinuedFraction(1, 1), ContinuedFraction(2, 1), ContinuedFraction(1, 2), ContinuedFraction(1, 3), ContinuedFraction(3, 1), ContinuedFraction(4, 1), ContinuedFraction(3, 2), ContinuedFraction(2, 3), ContinuedFraction(1, 4), ContinuedFraction(1, 5)]
>>> rats = rationals(enumeration="cantor diagonal", positive_only=False)
>>> first_ten_plus_zero = [next(rats) for _ in range(11)]
>>> first_ten_plus_zero
[ContinuedFraction(0, 1), ContinuedFraction(1, 1), ContinuedFraction(-1, 1), ContinuedFraction(2, 1), ContinuedFraction(-2, 1), ContinuedFraction(1, 2), ContinuedFraction(-1, 2), ContinuedFraction(1, 3), ContinuedFraction(-1, 3), ContinuedFraction(3, 1), ContinuedFraction(-3, 1)]
>>> rats = rationals(enumeration="cantor diagonal transposed")
>>> first_ten = [next(rats) for _ in range(10)]
>>> first_ten
[ContinuedFraction(1, 1), ContinuedFraction(1, 2), ContinuedFraction(2, 1), ContinuedFraction(3, 1), ContinuedFraction(1, 3), ContinuedFraction(1, 4), ContinuedFraction(2, 3), ContinuedFraction(3, 2), ContinuedFraction(4, 1), ContinuedFraction(5, 1)]
>>> rats = rationals(enumeration="cantor diagonal transposed", positive_only=False)
>>> first_ten_plus_zero = [next(rats) for _ in range(11)]
>>> first_ten_plus_zero
[ContinuedFraction(0, 1), ContinuedFraction(1, 1), ContinuedFraction(-1, 1), ContinuedFraction(1, 2), ContinuedFraction(-1, 2), ContinuedFraction(2, 1), ContinuedFraction(-2, 1), ContinuedFraction(3, 1), ContinuedFraction(-3, 1), ContinuedFraction(1, 3), ContinuedFraction(-1, 3)]
>>> rats = rationals(enumeration="rectilinear")
>>> first_ten = [next(rats) for _ in range(10)]
>>> first_ten
[ContinuedFraction(1, 1), ContinuedFraction(2, 1), ContinuedFraction(1, 2), ContinuedFraction(1, 3), ContinuedFraction(2, 3), ContinuedFraction(3, 2), ContinuedFraction(3, 1), ContinuedFraction(4, 1), ContinuedFraction(4, 3), ContinuedFraction(3, 4)]
>>> rats = rationals(enumeration="rectilinear", positive_only=False)
>>> first_ten_plus_zero = [next(rats) for _ in range(11)]
>>> first_ten_plus_zero
[ContinuedFraction(0, 1), ContinuedFraction(1, 1), ContinuedFraction(-1, 1), ContinuedFraction(2, 1), ContinuedFraction(-2, 1), ContinuedFraction(1, 2), ContinuedFraction(-1, 2), ContinuedFraction(1, 3), ContinuedFraction(-1, 3), ContinuedFraction(2, 3), ContinuedFraction(-2, 3)]
>>> rats = rationals(enumeration="rectilinear transposed", positive_only=False)
>>> first_ten_plus_zero = [next(rats) for _ in range(11)]
>>> first_ten_plus_zero
[ContinuedFraction(0, 1), ContinuedFraction(1, 1), ContinuedFraction(-1, 1), ContinuedFraction(1, 2), ContinuedFraction(-1, 2), ContinuedFraction(2, 1), ContinuedFraction(-2, 1), ContinuedFraction(3, 1), ContinuedFraction(-3, 1), ContinuedFraction(3, 2), ContinuedFraction(-3, 2)]
>>> rats = rationals(enumeration="some unknown enumeration")
>>> next(rats)
Traceback (most recent call last):
...
ValueError: The value of `enumeration` should be one of the following: "cantor diagonal", "cantor diagonal transposed", "rectilinear" or "rectilinear transposed".

continuedfractions.sequences.coprime_pairs(n: int, /) → Generator[tuple[int, int], None, None]

Generates a sequence (tuple) of all pairs \((a, b)\) of (positive) coprime integers \(a, b\) such that \(a, b <= n\).

It does not call on the search() method, which is not as fast as this one.

A ValueError is raised if n is not an int or is an int less than \(1\).

Parameters:

nint

The positive integer for which coprime pairs \((a, b)\), with \(1 \leq b < a \leq n\), are sought.

Yields:

tuple

A tuple of pairs of coprime integers \((a, b)\), with \(1 \leq b < a \leq n\).

Raises:

ValueError

If n is not an int or is an int less than \(1\).

Examples

A few examples of coprime pairs generation:

>>> tuple(coprime_pairs(1))
((1, 1),)
>>> tuple(coprime_pairs(2))
((1, 1), (2, 1))
>>> tuple(coprime_pairs(3))
((1, 1), (2, 1), (3, 1), (3, 2))
>>> tuple(coprime_pairs(5))
((1, 1), (2, 1), (3, 1), (3, 2), (4, 1), (4, 3), (5, 1), (5, 2), (5, 3), (5, 4))
>>> tuple(coprime_pairs(10))
((1, 1), (2, 1), (3, 1), (3, 2), (4, 1), (4, 3), (5, 1), (5, 2), (5, 3), (5, 4), (6, 1), (6, 5), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (8, 1), (8, 3), (8, 5), (8, 7), (9, 1), (9, 2), (9, 4), (9, 5), (9, 7), (9, 8), (10, 1), (10, 3), (10, 7), (10, 9))
>>> tuple(coprime_pairs("invalid input"))
Traceback (most recent call last):
...
ValueError: `n` must be a positive integer

class continuedfractions.sequences.FareyFraction(numerator=0, denominator=None)

A simple wrapper class for Farey fractions, subclassing ContinuedFraction.

continuedfractions.sequences.farey_sequence(n: int, /) → Generator[FareyFraction, None, None]

Generates an (ordered) sequence (tuple) of rational numbers forming the Farey sequence of order \(n\).

The elements of the sequence are yielded as FareyFraction instances, in ascending order of magnitude.

Parameters:

nint:

The order of the Farey sequence.

Yields:

FareyFraction

A sequence of FareyFraction instances representing the elements of the Farey sequence of order \(n\), in ascending order of magnitude.

Raises:

ValueError

If \(n\) is not a positive integer.

Examples

>>> tuple(farey_sequence(1))
(FareyFraction(0, 1), FareyFraction(1, 1))
>>> tuple(farey_sequence(2))
(FareyFraction(0, 1), FareyFraction(1, 2), FareyFraction(1, 1))
>>> tuple(farey_sequence(3))
(FareyFraction(0, 1), FareyFraction(1, 3), FareyFraction(1, 2), FareyFraction(2, 3), FareyFraction(1, 1))
>>> tuple(farey_sequence(4))
(FareyFraction(0, 1), FareyFraction(1, 4), FareyFraction(1, 3), FareyFraction(1, 2), FareyFraction(2, 3), FareyFraction(3, 4), FareyFraction(1, 1))
>>> tuple(farey_sequence(5))
(FareyFraction(0, 1), FareyFraction(1, 5), FareyFraction(1, 4), FareyFraction(1, 3), FareyFraction(2, 5), FareyFraction(1, 2), FareyFraction(3, 5), FareyFraction(2, 3), FareyFraction(3, 4), FareyFraction(4, 5), FareyFraction(1, 1))

class continuedfractions.sequences.KSRMTree

A class implementation of the Kanga-Saunders-Randall-Mitchell (KSRM) ternary trees for representing and generating pairs of all (positive) coprime integers.

The term “KSRM trees” is the author’s, and refers to the trees presented in the following papers:

• Kanga, A. R. (1990). The Family Tree of Pythagorean Triplets. The Mathematical Gazette, 26(15), 15-17.

• Mitchell, D. W. (2001). An Alternative Characterisation of All Primitive Pythagorean Triples. The Mathematical Gazette, 85(503), 273-275. https://doi.org/10.2307/3622017

• Saunders, R., & Randall, T. (1994). The family tree of the Pythagorean triplets revisited. The Mathematical Gazette, 78(482), 190-193. https://doi.org/10.2307/3618576

Note

The class is named KSRMTree purely for convenience, but it is actually a representation of two (ternary) subtrees.

Note

The author could not access the Kanga paper online, but the core result is described clearly in the papers of Saunders and Randall, and of Mitchell.

Attributes

branches	The tuple of three branch generating functions of the KSRM trees.
roots	The tuple of roots of the KSRM trees, which are \((2, 1)\) and \((3, 1)\).

Methods

search(n, /)	Depth-first branch-and-bound generative search function (in pre-order, NLMR) on the KSRM coprime pairs trees to find all pairs of coprime (positive) integers not exceeding the given integer \(n \geq 1\).
search_root(n, root, /)	Depth-first branch-and-bound generative search function (in pre-order, NLMR), with backtracking and pruning, on the KSRM coprime pairs trees, starting from the given root node.

property roots: Literal[2, 1, 3, 1]

The tuple of roots of the KSRM trees, which are \((2, 1)\) and \((3, 1)\).

For more details see the following papers:

• Kanga, A. R. (1990). The Family Tree of Pythagorean Triplets. The Mathematical Gazette, 26(15), 15-17.

• Mitchell, D. W. (2001). An Alternative Characterisation of All Primitive Pythagorean Triples. The Mathematical Gazette, 85(503), 273-275. https://doi.org/10.2307/3622017

• Saunders, R., & Randall, T. (1994). The family tree of the Pythagorean triplets revisited. The Mathematical Gazette, 78(482), 190-193. https://doi.org/10.2307/3618576

Examples

>>> KSRMTree().roots
((2, 1), (3, 1))

Type:

tuple

property branches: tuple[NamedCallableProxy]

The tuple of three branch generating functions of the KSRM trees.

There are three branch generating functions, given by the mappings:

\[\begin{split}\begin{align} (a, b) &\longmapsto (2a - b, a) \\ (a, b) &\longmapsto (2a + b, a) \\ (a, b) &\longmapsto (a + 2b, b) \end{align}\end{split}\]

For more details see the following papers:

• Kanga, A. R. (1990). The Family Tree of Pythagorean Triplets. The Mathematical Gazette, 26(15), 15-17.

• Mitchell, D. W. (2001). An Alternative Characterisation of All Primitive Pythagorean Triples. The Mathematical Gazette, 85(503), 273-275. https://doi.org/10.2307/3622017

• Saunders, R., & Randall, T. (1994). The family tree of the Pythagorean triplets revisited. The Mathematical Gazette, 78(482), 190-193. https://doi.org/10.2307/3618576

Examples

Generating the first two generations of children for the parent \((2, 1)\).

>>> tree = KSRMTree()
>>> tree.branches
(NamedCallableProxy("KSRM tree branch #1: (x, y) |--> (2x - y, x)"), NamedCallableProxy("KSRM tree branch #2: (x, y) |--> (2x + y, x)"), NamedCallableProxy("KSRM tree branch #3: (x, y) |--> (x + 2y, y)"))
>>> tree.branches[0](2, 1)
(3, 2)
>>> tree.branches[1](2, 1)
(5, 2)
>>> tree.branches[2](2, 1)
(4, 1)
>>> tree.branches[0](*tree.branches[0](2, 1))
(4, 3)
>>> tree.branches[1](*tree.branches[0](2, 1))
(8, 3)
>>> tree.branches[2](*tree.branches[0](2, 1))
(7, 2)
>>> tree.branches[0](*tree.branches[1](2, 1))
(8, 5)
>>> tree.branches[1](*tree.branches[1](2, 1))
(12, 5)
>>> tree.branches[2](*tree.branches[1](2, 1))
(9, 2)
>>> tree.branches[0](*tree.branches[2](2, 1))
(7, 4)
>>> tree.branches[1](*tree.branches[2](2, 1))
(9, 4)
>>> tree.branches[2](*tree.branches[2](2, 1))
(6, 1)

Type:

tuple

_backtrack(n: int, visited: list[tuple[tuple[int, int], NamedCallableProxy]], /, *, node_bound: int = None) → tuple[tuple[int, int], NamedCallableProxy, int, NamedCallableProxy]

Backtracks on the KSRM coprime pairs trees from a failed node to the nearest previously visited node that satisfies the node bound.

A private function that backtracks on the KSRM coprime pairs trees: the procedure is that, given a (positive) integer \(n > 2\), for which coprime pairs are being sought, and a sequence (list) of pairs of visited nodes and their associated generating branches in the KSRM tree, and assuming that the last element of the visited sequence contains the node that “failed”, the function identifies the nearest previously visited node whose first component satisifes the test \(< n\) and and whose associated generating branch is not equal to the third branch given by \((x, y) \longmapsto (x + 2y, y)\).

Note

The function assumes that the last node in the incoming sequence of visited nodes and generating branch pairs represents a “failed” node, i.e. whose first component failed the test \(\leq n\) during the search. No attempt is made to validate or verify the failed node, and the only purpose of the function is to backtrack to the nearest previously visited node which meets the requirements listed above.

Note

There is no input validation as this is a private function which will be called from search_root(). So results for invalid arguments will most likely be incorrect or unexpected.

Parameters:

nint

The (positive) integer \(> 2\) which is passed by the root search method or the general tree search method.

visitedlist

A sequence of visited nodes and associated generating branches in the KSRM coprime pairs tree.

node_boundint, default=None

A bound to check that \(a < n\) for a node \((a, b)\). The actual default value is the incoming \(n\), and this is set internally.

Returns:

tuple

A tuple consisting of the following values in order: (1) the target node in the visited sequence to backtrack to, (2) the associated generating branch function (the lambda for branch #1, or branch #2, or branch #3), (3) the index of the target node and branch pair in the visited sequence, (4) the generating branch of the successor node of the target node returned as (1).

Examples

An example where \(n = 5\) and the failed node is \((6, 1)\), which was the successor node to \((4, 1)\) from the third branch.

>>> tree = KSRMTree()
>>> tree.branches
(NamedCallableProxy("KSRM tree branch #1: (x, y) |--> (2x - y, x)"), NamedCallableProxy("KSRM tree branch #2: (x, y) |--> (2x + y, x)"), NamedCallableProxy("KSRM tree branch #3: (x, y) |--> (x + 2y, y)"))
>>> visited = [((2, 1), None), ((4, 1), tree.branches[-1]), ((6, 1), tree.branches[-1])]
>>> tree._backtrack(5, visited)
((2, 1), None, 0, NamedCallableProxy("KSRM tree branch #3: (x, y) |--> (x + 2y, y)"))

An example where \(n = 8\) and the failed node is \((19, 8)\), which was the successor node to \((8, 3)\) from the first branch.

>>> tree = KSRMTree()
>>> tree.branches
(NamedCallableProxy("KSRM tree branch #1: (x, y) |--> (2x - y, x)"), NamedCallableProxy("KSRM tree branch #2: (x, y) |--> (2x + y, x)"), NamedCallableProxy("KSRM tree branch #3: (x, y) |--> (x + 2y, y)"))
>>> visited = [((2, 1), None), ((3, 2),tree.branches[0]), ((8, 3),tree.branches[1]), ((19, 8), tree.branches[0])]
>>> tree._backtrack(8, visited)
((3, 2), NamedCallableProxy("KSRM tree branch #1: (x, y) |--> (2x - y, x)"), 1, NamedCallableProxy("KSRM tree branch #2: (x, y) |--> (2x + y, x)"))

search_root(n: int, root: tuple[int, int], /) → Generator[tuple[int, int], None, None]

Depth-first branch-and-bound generative search function (in pre-order, NLMR), with backtracking and pruning, on the KSRM coprime pairs trees, starting from the given root node.

The given root node need not be the canonical roots, \((2, 1)\), \((3, 1)\), but can be any of their successor nodes.

It is required that \(n \geq 2\), otherwise a ValueError is raised.

The search implementation is an iterative version of a depth-first branch-and-bound search (DFS) procedure, with backtracking and pruning, in which nodes are traversed in NLMR pre-order (root -> left -> mid -> right) and bounds and checks are applied to the nodes, including pruning failed or unnecessary nodes, before further traversal or backtracking:

1. Visit the current node \((a, b)\) and check \(a \leq n\).

2. If the check is successful iteratively traverse the current node’s first child and its children, then the second child and its children, and then the third child and its children, applying the check \(a \leq n\) to each visited node.

3. If a check fails for any node backtrack to the nearest previously visited node which meets a stricter check \(a < n\) and which has unvisited child nodes, while pruning all visited intermediate nodes after the backtracked target node and leading up to the failed node, including the failed node. By design the backtracked target node will have untraversed children on at least one branch, and the traversal can begin again, as described above.

Parameters:

nint

The positive integer for which coprime pairs \((a, b)\), with \(1 \leq b < a \leq n\), are sought.

roottuple

The “root” node from which to search - this can be either of the canonical roots, \((2, 1)\), \((3, 1)\), but also any of their successor nodes.

Yields:

tuple

Pairs of coprime integers \((a, b)\), with \(1 \leq b < a \leq n\).

Raises:

ValueError

If n is not an integer or is \(< 2\).

Examples

Searching from the root \((2, 1)\) for coprime pairs for \(n = 5\):

>>> tree = KSRMTree()
>>> list(tree.search_root(5, (2, 1)))
[(2, 1), (3, 2), (4, 3), (5, 4), (5, 2), (4, 1)]
>>> assert tree.roots[0] == (2, 1)
>>> list(tree.search_root(5, tree.roots[0]))
[(2, 1), (3, 2), (4, 3), (5, 4), (5, 2), (4, 1)]

The same type of search from the root \((3, 1)\):

>>> list(tree.search_root(5, (3, 1)))
[(3, 1), (5, 3), (5, 1)]
>>> assert tree.roots[1] == (3, 1)
>>> list(tree.search_root(5, tree.roots[1]))
[(3, 1), (5, 3), (5, 1)]

search(n: int, /) → Generator[tuple[int, int], None, None]

Depth-first branch-and-bound generative search function (in pre-order, NLMR) on the KSRM coprime pairs trees to find all pairs of coprime (positive) integers not exceeding the given integer \(n \geq 1\).

See the search_root() method for details of the implementation for the root-based search.

This method mainly calls the root-based search method search_root() for the two canonical roots \((2, 1)\) and \((3, 1)\).

The two KSRM trees are actually only traversed if \(n > 3\).

Parameters:

nint

The positive integer for which coprime pairs \((a, b)\), with \(1 \leq b < a \leq n\), are sought.

Yields:

tuple

Pairs of coprime integers \((a, b)\), with \(1 \leq b < a \leq n\).

Raises:

ValueError

If n is not an integer or is \(< 1\).

Examples

A few examples of invalid and valid searches:

>>> tree = KSRMTree()
>>> list(tree.search("not an integer"))
Traceback (most recent call last):
...
ValueError: `n` must be a positive integer.
>>> list(tree.search(1))
[(1, 1)]
>>> list(tree.search(2))
[(1, 1), (2, 1)]
>>> list(tree.search(3))
[(1, 1), (2, 1), (3, 2), (3, 1)]
>>> list(tree.search(5))
[(1, 1), (2, 1), (3, 2), (4, 3), (4, 1), (3, 1), (5, 4), (5, 3), (5, 2), (5, 1)]
>>> list(tree.search(10))
[(1, 1), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (9, 8), (8, 3), (7, 2), (5, 2), (8, 5), (9, 2), (4, 1), (7, 4), (9, 4), (6, 1), (8, 1), (3, 1), (5, 3), (7, 5), (9, 7), (7, 3), (5, 1), (9, 5), (7, 1), (9, 1), (10, 9), (10, 7), (10, 3), (10, 1)]