lib.numbertheory Package

A collection of various number-theoretic functions covering basis numeric properties, divisors of integers, primality testing, prime number sieving and integer factorisation.

Where these primitives may have many algorithms (e.g. integer factorisation), a collection of algorithms may be included but there will be an overarching interface that is designed to be optimised for many inputs. These higher-level functions will utilise appropriate algorithms depending on the input values.

lib.numbertheory – A collection of number-theoretic functions

lib.numbertheory.divisor_count(n)

Compute \(\sigma_0(n)=\Sigma_{d|n}1\); the number of all divisors of \(n\)

Parameters:

n (int) – integer input

Return type:

int

Returns:

\(\sigma_0(n)\)

Raises:
  • TypeError – if \(n\) is not an int variable
  • ValueError – if \(n\) is not positive
>>> divisor_count(17)
2
>>> divisor_count(10)
4
lib.numbertheory.divisor_sum(n)

Compute \(\sigma_1(n)=\Sigma_{d|n}d\); the sum of all divisors of \(n\)

Parameters:

n (int) – integer input

Return type:

int

Returns:

\(\sigma_1(n)\)

Raises:
  • TypeError – if \(n\) is not an int variable
  • ValueError – if \(n\) is not positive
>>> divisor_sum(17)
18
>>> divisor_sum(10)
18
lib.numbertheory.divisor_sum_aliquot(n)

Compute \(s(n)=\sigma_1(n)-n\); the sum of all proper divisors of \(n\)

Parameters:

n (int) – integer input

Return type:

int

Returns:

\(s(n)\)

Raises:
  • TypeError – if \(n\) is not an int variable
  • ValueError – if \(n\) is not positive
>>> divisor_sum_aliquot(17)
1
>>> divisor_sum_aliquot(10)
8
lib.numbertheory.divisors_sieve(upper_bound, proper, aggregate=None)

An iterator over the sets of divisors of \(n\), for \(n \in [1, upper\_bound]\)

The obvious way to generate the divisors of a given integer \(n\) is to factorise that integer. We can then enumerate the product of all possible subsets of this factorisation, giving all divisors of \(n\).

In general, there is nothing wrong with this approach. However, if you require the divisors of a sequence of contiguous numbers then sieving will be an overall better approach.

A prime sieve is an efficient way to enumerate primes up to some upper bound. The same principle can be adopted to enumerate not just primality but all divisors for this range of numbers.

The standard operation of this function allows these divisors to be accessed explicitly. However, it is quite common to apply aggregation functions to these divisor sets with the individual divisors being irrelevant. Common aggregations have been implemented inside this function and for performance reasons and it is recommended they be used instead of implementations in consuming code. The following values for aggregation are supported:

  • 'count' - the number of the divisors of \(n\)
  • 'sum' - the sum of the divisors of \(n\)

Note

the memory requirements for this sieve is \(O(upper\_bound)\).

Parameters:
  • upper_bound (int) – the upper bound of the divisors sieve
  • proper (bool) – whether to iterate over just proper divisors or not
  • aggregate (Optional[str]) – an optional aggregation to apply to the divisors of each \(n\)
Return type:

Iterator[int]

Returns:

an iterator of the sets of divisors/results of aggregation produced by the sieve in ascending order

Raises:
  • TypeError – if upper_bound is not an int variable
  • ValueError – if upper_bound is not positive
  • TypeError – if aggregate is not None or a str variable
  • ValueError – if a str-valued aggregate is not 'count' or 'sum'
>>> for n, divisors in enumerate(divisors_sieve(8, proper=False)):
>>>     print('The divisors of {} are {}.'.format(n + 1, divisors))
The divisors of 1 are {1}.
The divisors of 2 are {1, 2}.
The divisors of 3 are {1, 3}.
The divisors of 4 are {1, 2, 4}.
The divisors of 5 are {1, 5}.
The divisors of 6 are {1, 2, 3, 6}.
The divisors of 7 are {1, 7}.
The divisors of 8 are {8, 1, 2, 4}.
>>> for n, n_divisors in enumerate(divisors_sieve(8, proper=False, aggregate="count")):
>>>     print('The number of divisors of {} is {}.'.format(n + 1, n_divisors))
The number of divisors of 1 is 1.
The number of divisors of 2 is 2.
The number of divisors of 3 is 2.
The number of divisors of 4 is 3.
The number of divisors of 5 is 2.
The number of divisors of 6 is 4.
The number of divisors of 7 is 2.
The number of divisors of 8 is 4.
>>> for n, divisor_sum in enumerate(divisors_sieve(8, proper=False, aggregate="sum")):
>>>     print('The sum of the divisors of {} is {}.'.format(n + 1, divisor_sum))
The sum of the divisors of 1 is 1.
The sum of the divisors of 2 is 3.
The sum of the divisors of 3 is 4.
The sum of the divisors of 4 is 7.
The sum of the divisors of 5 is 6.
The sum of the divisors of 6 is 12.
The sum of the divisors of 7 is 8.
The sum of the divisors of 8 is 15.
lib.numbertheory.factor(n)

Compute the factorisation of \(n\) given by \(n=\prod_{i} p_i^{e_i}\), \(p_i \in \mathbb{N}\)

Note

a variety of algorithms are used to try to balance the performance of this factorisation function across many inputs. These algorithms include detecting prime inputs, perfect prime powers, trial division and Fermat’s factoring algorithm.

Parameters:n (int) – the integer to be factored
Return type:Dict[int, int]
Returns:the factorisation of \(n\) as the dictionary {\(p_i\): \(e_i\)}
Raises:TypeError – if \(n\) is not an int variable
>>> factor(7)
{7: 1}
>>> factor(88550)
{2: 1, 7: 1, 5: 2, 11: 1, 23: 1}
lib.numbertheory.is_even(n)

Determine whether \(n\) is even

Parameters:n (int) – the integer to test
Return type:bool
Returns:whether \(n\) is even or not
Raises:TypeError – if \(n\) is not an int variable
>>> is_even(4)
True
>>> is_even(7)
False
>>> is_even(-2)
True
lib.numbertheory.is_odd(n)

Determine whether \(n\) is odd

Parameters:n (int) – the integer to test
Return type:bool
Returns:whether \(n\) is odd or not
Raises:TypeError – if \(n\) is not an int variable
>>> is_odd(4)
False
>>> is_odd(7)
True
>>> is_odd(-2)
False
lib.numbertheory.is_probably_prime(n, k=20)

Determine whether \(n\) is probably prime

According to Wikipedia, a probable prime is:
an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers

Put another way, all prime numbers are probable primes but most composite numbers are not probable primes. A probabilistic primality testing algorithm takes as input an integer \(n\) which can be tested for primality and produces an answer with a bounded error rate very quickly, even for large \(n\). Probabilistic primality testing algorithms are often favoured over primality proving algorithms for efficiency reasons, given the error margin can be bounded by a vanishingly small threshold.

This function will apply some very simple tests to determine whether \(n\) is negative, a small prime, or divisible by a small prime. In these cases, \(n\) is determined to be composite, prime, or composite respectively.

If these tests fail to reveal a conclusive answer, the Miller-Rabin probabilistic primality testing algorithm is applied for the specified number of iterations \(k\).

Parameters:
  • n (int) – the number to test for primality
  • k (int) – the number of Miller-Rabin iterations to use, if necessary (default is \(20\))
Return type:

bool

Returns:

whether \(n\) is probably prime or not

Raises:

TypeError – if \(n\) or \(k\) are not int variables

>>> is_probably_prime(123)
True
>>> is_probably_prime(13 * 17)
False

Note

the Miller-Rabin algorithm may incorrectly call a composite “probably prime” with probability no greater than \(4^{-k}\). The default value of \(20\) for \(k\) bounds the error rate to \(2^{-40}\), although in practice the expected error rate for any individual input is generally far lower.

lib.numbertheory.is_square(n)

Determine whether \(n\) is a perfect square, i.e. \(n=m^2\) s.t. \(\exists m \in \mathbb{Z}\)

Parameters:n (int) – the integer to test
Return type:bool
Returns:whether \(n\) is a perfect square or not
Raises:TypeError – if \(n\) is not an int variable
>>> is_square(9)
True
>>> is_square(11)
False
lib.numbertheory.prime_sieve(upper_bound)

Build an iterator over a prime sieve up to a specified bound

A prime sieve is an efficient way to enumerate primes up to some upper bound. Depending on the size of upper_bound either the Sieve of Eratosthenes is used directly or its segmented variant is.

Let \(n\) be upper_bound. The memory requirements for the sieve of Eratosthenes is \(O(n)\) while the memory requirements for the segmented sieve of Eratosthenes is \(O(m)\) for a segment size of \(m\). This implementation sets \(m=\sqrt n\) which allows the segmented variant to scale for particularly large values of upper_bound that may not easily fit into memory for the standard sieve.

Parameters:

upper_bound (int) – the upper bound of the prime sieve

Return type:

Iterator[int]

Returns:

an iterator to the primes produced by the sieve in ascending order

Raises:
  • TypeError – if upper_bound is not an int variable
  • ValueError – if upper_bound is not positive