lib.sequence
Module¶
The sequences defined in this module fall into one of two categories:
- Sequential access (inherited from
collections.abc.Iterator
) - Random access (inherited from
collections.abc.Sequence
)
Sequentially accessible sequences must be computed from their start through to the desired element; they are typically defined by recurrence relations or where the elements of a sequence don’t have a well-defined ordering. Alternatively, randomly accessible sequences support access to arbitrary elements from the sequence without having computed all previous elements first.
As per the Python standard library, objects derived from collections.abc.Iterator
implement the iterator protocol,
meaning they represent a stream of data that will be iterated over precisely once. They do not support indexing.
Objects derived from collections.abc.Sequence
implement the iterator protocol, however, they also support indexing
and having their length evaluated (via the standard len
function).
Note
this module includes some infinite sequences derived from collections.abc.Sequence
. While this means the
standard len
function may be evaluated on them, they will raise a TypeError
as per Python conventions.
For some sequences, there is an efficient membership test to determine whether a given number belongs to that sequence.
These tests can be accessed via Python’s in
operator. Those sequences with such functionality will include sample
code illustrating the behaviour; the computational complexity will also be included in a note in the relevant class
documentation.
Observe that many of these sequences are of infinite length, however, applications will only need some finite length sub-sequence. There are of course many ways to implement this, however, the following example to print all Fibonacci numbers less than \(1000\) illustrates a concise design pattern that can be adopted:
from itertools import takewhile
from lib.sequence import Fibonaccis
for elt in takewhile(lambda f_n: f_n < 1000, Fibonaccis()):
print(elt)
The itertools.takewhile
function will consume from an iterator while elements satisfy the given predicate (i.e. the
provided function returns True
when evaluated on elements in the given sequence). The first element encountered that
violates the predicate will terminate the iteration.
lib.sequence
– A collection of sequence abstractions¶
-
class
lib.sequence.
Divisors
(n, proper)¶ Bases:
collections.abc.Iterator
All positive integer divisors of \(n\), i.e. \(\lbrace d_i \rbrace \mbox{ } \forall d_i \in \mathbb{N} \mbox{ s.t. } d_i \vert n\)
This sequence can be used to iterate over all divisors of \(n\), or just the proper divisors of \(n\) by providing a suitable value for the proper parameter.
Note
the proper divisors of \(n\) do not include \(n\) itself.
Parameters: - n (
int
) – the target integer - proper (
bool
) – whether to iterate over just proper divisors or not
Raises: - TypeError – if \(n\) is not an
int
variable - TypeError – if proper is not a
bool
variable - ValueError – if \(n \le 0\)
- TypeError – if a variable is tested for membership of this sequence that is not of type
int
/float
>>> list(Divisors(10, proper=True)) [1, 2, 5] >>> list(Divisors(10, proper=False)) [1, 2, 5, 10] >>> len(Divisors(10, proper=True)) 3 >>> len(Divisors(10, proper=False)) 4 >>> 5 in Divisors(10, proper=True) True >>> 7 in Divisors(10, proper=False) False
- n (
-
class
lib.sequence.
DivisorsRange
(upper_bound, proper)¶ Bases:
collections.abc.Iterator
The sequence of the sets of divisors of \(n\), for \(n \in [1, upper\_bound]\)
Each element in this sequence contains all the positive integer divisors of \(n\), i.e. \(\lbrace d_i \rbrace \mbox{ } \forall d_i \in \mathbb{N} \mbox{ s.t. } d_i \vert n\) for the range \(n \in [1, upper\_bound]\).
This sequence can be used to iterate over all divisors of \(n\), or just the proper divisors of \(n\) by providing a suitable value for the proper parameter.
Note
the proper divisors of \(n\) do not include \(n\) itself.
Parameters: - upper_bound (
int
) – the target integer - proper (
bool
) – whether to iterate over just proper divisors or not
Raises: - TypeError – if \(upper\_bound\) is not an
int
variable - TypeError – if proper is not a
bool
variable - ValueError – if \(upper\_bound \le 0\)
>>> list(DivisorsRange(10, proper=True)) [{1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}] >>> list(DivisorsRange(10, proper=False)) [{1}, {1, 2}, {1, 3}, {1, 2, 4}, {1, 5}, {1, 2, 3, 6}, {1, 7}, {8, 1, 2, 4}, {1, 3, 9}, {1, 10, 2, 5}]
Note
this sequence may be considered redundant given the existing
lib.sequence.Divisors
sequence. Thelib.sequence.DivisorsRange
sequence is provided for the case when considering the divisors of a range of numbers, and not just a single number. In the case of a contiguous range of inputs, thelib.sequence.DivisorsRange
will provide superior performance due to its use of sieving techniques.- upper_bound (
-
class
lib.sequence.
Factorials
¶ Bases:
collections.abc.Iterator
The factorial numbers: \(\lbrace n! \rbrace_{n=0}^{\infty}\) where \(n! = n \times (n-1) \times \dots \times 1\) and \(0! = 1\)
Note
checking whether an integer \(x\) is a factorial number has computational complexity \(O(\log x)\)
Raises: - TypeError – if this sequence is indexed by a variable that is not of type
int
- ValueError – if this sequence is indexed by an
int
variable with a negative value - TypeError – if a variable is tested for membership of this sequence that is not of type
int
/float
>>> list(itertools.takewhile(lambda x: x < 1000, Factorials())) [1, 1, 2, 6, 24, 120, 720] >>> 24 in Factorials() True >>> 25 in Factorials() False
- TypeError – if this sequence is indexed by a variable that is not of type
-
class
lib.sequence.
Fibonaccis
¶ Bases:
collections.abc.Iterator
The Fibonacci numbers: \(\lbrace F_n \rbrace_{n=0}^{\infty}\) where \(F_n = F_{n-1} + F_{n-2} \mbox{ } \forall n \ge 2\) and \(F_0 = 0, F_1 = 1\)
Note
checking whether an integer \(x\) is a Fibonacci number has computational complexity \(O(\log x)\)
Raises: - TypeError – if this sequence is indexed by a variable that is not of type
int
- ValueError – if this sequence is indexed by an
int
variable with a negative value - TypeError – if a variable is tested for membership of this sequence that is not of type
int
/float
>>> list(itertools.takewhile(lambda x: x < 50, Fibonaccis())) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] >>> 20 in Fibonaccis() False >>> 21 in Fibonaccis() True
- TypeError – if this sequence is indexed by a variable that is not of type
-
class
lib.sequence.
Figurates
¶ Bases:
collections.abc.Sequence
An abstract base class for figurate numbers
Warning
this class cannot be instantiated directly, use one of the concrete children classes:
Warning
this class is derived from
collections.abc.Sequence
, so it must implement a__len__
method to allow any instance to be evaluated in the standardlen
function. However, figurate sequences are infinite. By Python convention, this class (and all of its children) will raise aTypeError
when evaluated bylen
.
-
class
lib.sequence.
Hexagonals
¶ Bases:
lib.sequence.Figurates
The hexagonal numbers: \(\lbrace h_n \rbrace_{n=1}^{\infty}\) where \(h_n = n (2n - 1)\)
Note
checking whether an integer \(x\) is hexagonal has computational complexity \(O(\log \log x)\)
Raises: - TypeError – if this sequence is indexed by a variable that is not of type
int
- TypeError – if a variable is tested for membership of this sequence that is not of type
int
/float
>>> list(itertools.takewhile(lambda x: x < 100, Hexagonals())) [1, 6, 15, 28, 45, 66, 91] >>> len(Hexagonals()) TypeError: object of type '<class 'lib.sequence.Hexagonals'>' has infinite length >>> 15 in Hexagonals() True >>> 30 in Hexagonals() False
- TypeError – if this sequence is indexed by a variable that is not of type
-
class
lib.sequence.
Pandigitals
(n)¶ Bases:
collections.abc.Iterator
A decimal \(n\)-pandigital number contains the digits \(1\) through \(d\) precisely once.
For example, \(51243\) is a \(5\)-pandigital number while \(61\) is not.
Parameters: n (
int
) – the pandigital parameter \(n\)Raises: - TypeError – if \(n\) is not an
int
variable - ValueError – if \(n \le 0\)
>>> list(Pandigitals(3)) [123, 132, 213, 231, 312, 321] >>> len(Pandigitals(6)) 720
- TypeError – if \(n\) is not an
-
class
lib.sequence.
Pentagonals
¶ Bases:
lib.sequence.Figurates
The pentagonal numbers: \(\lbrace p_n \rbrace_{n=1}^{\infty}\) where \(p_n = \frac{n (3n - 1)}{2}\)
Note
checking whether an integer \(x\) is pentagonal has computational complexity \(O(\log \log x)\)
Raises: - TypeError – if this sequence is indexed by a variable that is not of type
int
- TypeError – if a variable is tested for membership of this sequence that is not of type
int
/float
>>> list(itertools.takewhile(lambda x: x < 100, Pentagonals())) [1, 5, 12, 22, 35, 51, 70, 92] >>> len(Pentagonals()) TypeError: object of type '<class 'lib.sequence.Pentagonals'>' has infinite length >>> 11 in Pentagonals() False >>> 22 in Pentagonals() True
- TypeError – if this sequence is indexed by a variable that is not of type
-
class
lib.sequence.
Primes
(upper_bound=None, n_primes=None)¶ Bases:
collections.abc.Iterator
The prime numbers: \(\lbrace p_i \rbrace_{n=1}^{l}\) where \(p_i\) is the \(i^{th}\) prime number and the bound \(l\) is defined as follows
Note
a prime number \(p \in \mathbb{N}\) is only divisible by itself and \(1\).
This sequence builds an iterator over the prime numbers by use of a sieving algorithm and so a finite bound must be specified. This bound may be either of:
- all prime numbers up to, and including, upper_bound; or
- the first n_primes prime numbers, in ascending order.
Warning
you must specify precisely one of upper_bound or n_primes, but not both.
Parameters: - upper_bound (
Optional
[int
]) – the upper bound of primes in the sequence - n_primes (
Optional
[int
]) – the number of primes in the sequence
Raises: - TypeError – if \(upper\_bound\) is not an
int
variable - TypeError – if \(n\_primes\) is not an
int
variable - ValueError – if \(upper\_bound \le 0\)
- ValueError – if \(n\_primes \lt 0\)
>>> list(Primes(upper_bound=10)) [2, 3, 5, 7] >>> list(Primes(n_primes=10)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
-
class
lib.sequence.
Triangulars
¶ Bases:
lib.sequence.Figurates
The triangular numbers: \(\lbrace T_n \rbrace_{n=1}^{\infty}\) where \(T_n = \frac{n (n + 1)}{2}\)
Note
checking whether an integer \(x\) is triangular has computational complexity \(O(\log \log x)\)
Raises: - TypeError – if this sequence is indexed by a variable that is not of type
int
- TypeError – if a variable is tested for membership of this sequence that is not of type
int
/float
>>> list(itertools.takewhile(lambda x: x < 50, Triangulars())) [1, 3, 6, 10, 15, 21, 28, 36, 45] >>> len(Triangulars()) TypeError: object of type '<class 'lib.sequence.Triangulars'>' has infinite length >>> 10 in Triangulars() True >>> 20 in Triangulars() False
- TypeError – if this sequence is indexed by a variable that is not of type