API documentation

The nmutils package contains four modules:

nmutils.miller_rabin

class nmutils.miller_rabin.MillerRabin

Miller-Rabin primality test

Deterministic implementation of Miller-Rabin primality test, based on https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Class loads primes below 5,000. For given n, assuming n odd (returning False if n is not 2 otherwise), trial division is first attempted versus these initial primes.

If trial division fails to identify primality, the full Miller-Rabin algorithm is employed, with witnesses chosen based on the value of n.

Empirically, the MillerRabin class appears to out-perform trial division for primes larger than 1,000,000 (trial division tested all primes up to 1,000,000 in just over 6s; Miller-Rabin achieved the same in just under 6s).

is_prime()

Return primality of n

Uses trial division for small n and Miller-Rabin for larger values.

>>> mr = MillerRabin()

>>> mr.is_prime(15)
False

>>> mr.is_prime(17)
True

nmutils.primes

Module containing functions to identify primes, generate primes, and factorize numbers into primes

exception nmutils.primes.PrimeError

Base class for exceptions raised by prime functions

nmutils.primes.get_prime_factors(n)

Return list of (non-unique) prime factors of n

>>> get_prime_factors(100)
[2, 2, 5, 5]
nmutils.primes.get_primes_under_n(n)

Return list of primes less than n

>>> get_primes_under_n(23)
[2, 3, 5, 7, 11, 13, 17, 19]
nmutils.primes.get_primes_up_to_n(n)

Return list of primes up to and including n

>>> get_primes_up_to_n(23)
[2, 3, 5, 7, 11, 13, 17, 19, 23]
nmutils.primes.get_unique_prime_factors(n)

Return list of unique prime factors of n

>>> get_unique_prime_factors(100)
[2, 5]
nmutils.primes.is_prime(n, known_primes=None)

Return primality of n

If a list of known primes is passed then these are checked as potential factors, else all numbers from 2 up to the square root of n are checked.

A list of known primes should be passed in sorted order (this is not checked for performance reasons, it is the user’s responsibility to ensure primes are passed in sorted order), but a PrimeError is thrown if the largest prime is less than the square root of n.

>>> is_prime(5)
True

>>> is_prime(6)
False

>>> primes = [2, 3, 5]
>>> is_prime(17, primes)
True

>>> is_prime(37, primes)  # doctest: +NORMALIZE_WHITESPACE
Traceback (most recent call last):
    ...
nmutils.primes.PrimeError: Known primes passed must be at least as
great as square root of n (max prime = 5, square root of n = 6)

nmutils.pythagorean_triples

class nmutils.pythagorean_triples.PythagoreanTripleGenerator

Class that continuously generates distinct, primitive Pythagorean triples

Source: https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples

The class stores triples in a priority queue; triples are stored from smallest to largest, where size is taken as the sum of the elements of the triple (so if the triple were considered to form a right-angled triangle then the “size” would be equal to the sum of the side lengths, i.e. the perimeter)

>>> ptg = PythagoreanTripleGenerator()

>>> ptg.GetNextTriple()
(3, 4, 5)

>>> ptg.GetNextTriple()
(5, 12, 13)

nmutils.sqrt_expansion

class nmutils.sqrt_expansion.SqrtExpansion(n, iterable=None)

Generates square root expansion of an irrational number

>>> expansion = SqrtExpansion(24)

>>> expansion.root
4

>>> expansion.key
(1, 8)

>>> expansion = SqrtExpansion(25)
Traceback (most recent call last):
    ...
ValueError: Input to SqrtExpansion cannot be a square
coefficient(n)

Return nth element of key, allowing repeats where n > period

>>> expansion = SqrtExpansion(24)

>>> expansion.coefficient(3)
8

>>> expansion.coefficient(4)
1
get_nth_fraction(n)

Return nth fractional estimate of square root of n

>>> expansion = SqrtExpansion(24)

>>> expansion.get_nth_fraction(1)
Fraction(4, 1)

>>> expansion.get_nth_fraction(2)
Fraction(5, 1)

>>> expansion.get_nth_fraction(3)
Fraction(44, 9)

>>> expansion.get_nth_fraction(4)
Fraction(49, 10)
static get_root_and_key(n)

Return square root expansion root and key for square root of n

>>> SqrtExpansion.get_root_and_key(24)
(4, (1, 8))
property period

Return length of key

>>> expansion = SqrtExpansion(24)

>>> expansion.period
2