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
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. The lib.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, the lib.sequence.DivisorsRange will provide superior performance due to its use of sieving techniques.

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
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
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 standard len function. However, figurate sequences are infinite. By Python convention, this class (and all of its children) will raise a TypeError when evaluated by len.

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
class lib.sequence.Pandigitals(n)

Bases: collections.abc.Iterator

The pandigital numbers

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
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
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