Module for basic math in the general vicinity of computational number theory

## labmath version 1.0.8

This is a module for basic math in the general vicinity of computational number theory. It includes functions associated with primality testing, integer factoring, prime counting, linear recurrences, modular square roots, generalized Pell equations, the classic arithmetical functions, continued fractions, partitions, Størmer’s theorem, smooth numbers, and Dirichlet convolution. Integer arithmetic is used wherever feasible.

## Functions

We make a few imports:

```from multiprocessing import Process, Queue as mpQueue
from itertools import chain, count, groupby, islice, tee, cycle, takewhile, compress, product
from fractions import Fraction
from random import randrange
from math import log, sqrt; inf = float('inf')
from heapq import merge

try: from gmpy2 import mpz; mpzv, inttypes = 2, (int, type(mpz(1)))
except ImportError: mpz, mpzv, inttypes = int, 0, (int,)
```

The new functions provided by this module are as follows. Further details, including examples and input details, are available in docstrings and accessible via the built-in help function.

```primegen(limit=inf)
```

Generates primes less than the given limit (which may be infinite) lazily via a segmented sieve of Eratosthenes. Uses O(√p) memory, where p is the most recently yielded prime.

```rpn(instr)
```

Evaluates a string in reverse Polish notation. The acceptable binary operators are + - * / // % ** and correspond directly to those same operators in Python3 source code. The acceptable unary operators are ! #. They are the factorial and primorial, respectively. There are three aliases: x for * , xx for ** , and p! for #.

```iterprod(l)
```

Product of the elements of any iterable. The product of an empty iterable is 1.

```listprod(l)
```

Product of the elements of a list. The product of the empty list is 1. We use a binary algorithm because this can easily generate huge numbers, and calling reduce(lambda x,y: x*y, a) in such situations is quite a bit slower due to the time-complexity of multiplication. However, the size of the problem required to make this superior to iterprod() is quite large, so iterprod() should usually be used instead.

```binomial(n,k)
```

The binomial coefficient nCr(n, k).

```powerset(l)
```

Generates the powerset of a list, tuple, or string. The yielded objects are always lists.

```primephi(x, a, ps, phicache={})
```

Legendre’s phi function. Helper function for primepi.

```primepi(x, ps=[], picache={}, phicache={}, sqrts={})
```

Computes the number of primes ≤ x via the Meissel-Lehmer method. The arguments ps, pichache, phicache, and sqrts are for internal use only.

```primesum(n)
```

Sum of primes ≤ n.

```altseriesaccel(a, n)
```

Convergence acceleration for alternating series. This is algorithm 1 from Convergence Acceleration of Alternating Series by Cohen, Villegas, and Zagier (pdf), with a minor tweak so that the d-value isn’t computed via floating point.

```riemannzeta(n, k=24)
```

Computes the Riemann zeta function by applying altseriesaccel to the Dirichlet eta function. Should be rather accurate throughout the complex plane except near n such that 1 = 2n-1.

```zetam1(n, k=24)
```

Computes riemannzeta(n, k) - 1 by applying altseriesaccel to the Dirichlet eta function. Designed to be accurate even when riemannzeta(n) is machine-indistinguishable from 1.0 — in particular, when n is a large real number.

```riemannR(x, n=None, zc={})
```

Uses the Gram series to compute Riemann’s R function, which is a rather good approximation to primepi. The argument zc is a cache of zeta values.

```nthprimeapprox(n)
```

Produces an integer that should be rather close to the nth prime by using binary splitting on Riemann’s R function.

```nthprime(n)
```

Returns the nth prime (counting 2 as #1). This is done with some efficiency by using nthprimeapprox as an initial estimate, computing primepi of that, and then sieving to remove the error.

```gcd(a, *r)
```

Greatest common divisor of any number of values.

```xgcd(a, b)
```

Extended Euclidean altorithm: returns a tuple (g, x, y) such that g = gcd(a, b) and g = a·x + b·y.

```modinv(a, m)
```

Returns the inverse of a modulo m, normalized to lie between 0 and m-1. If a is not coprime to m, returns 1.

```crt(rems, mods)
```

Returns the unique integer c in range(iterprod(mods)) such that cx (mod y) for (x, y) in zip(rems, mods). All elements of mods must be pairwise coprime.

```lcm(a, *r)
```

The least common multiple of any number of values.

```isqrt(n)
```

Greatest integer whose square is ≤ n.

```introot(n, r=2)
```

For non-negative n, returns the greatest integer ≤ the rth root of n. For negative n, returns the least integer ≥ the rth root of n, or None if r is even.

```ispower(n, r=0)
```

If r = 0: If n is a perfect power, return a tuple containing the largest integer that, when squares/cubed/etc, yields n as the first component and the relevant power as the second component. If n is not a perfect power, return None.

If r > 0: We check whether n is a perfect rth power; we return its rth root if it is and None if it isn’t.

```ilog(x, b)
```

Greatest integer k such that bkx.

```fibogen()
```

Generates the Fibonacci numbers.

```fibo(n, f={0:0, 1:1, 2:1})
```

Efficiently extracts the nth Fibonacci number, indexed so that fibo(0) = 0 and fibo(1) = fibo(2) = 1. The argument f is used for memoization. We compute O(log(n)) earlier Fibonaccis along the way. This is the asymptotically fastest algorithm.

```fibomod(n, m, f={0:0, 1:1, 2:1})
```

Efficiently extracts the nth Fibonacci number modulo m, indexed so that fibo(0) = 0 and fibo(1) == fibo(2) = 1. The argument f is used for memoization. We compute O(log(n)) earlier Fibonaccis along the way. This is the asymptotically fastest algorithm.

```lucaschain(n, x0, x1, op1, op2)
```

Algorithm 3.6.7 from Prime Numbers: A Computational Perspective by Crandall & Pomerance (2nd edition): Evaluation of a binary Lucas chain. To quote their description:

For a sequence x0, x1, … with a rule for computing x2j from xj and a rule for computing x2j+1 from xj and xj+1, this algorithm computes (xn, xn+1) for a given positive integer n. We have n in binary as (n0, n1, …, nb-1) with n0 being the low-order bit. We write the rules as follows: x2j = op1(xj) and x2j+1 = op2(xj, xj+1).
```lucasgen(P, Q):
```

Generates the Lucas U- and V-sequences with parameters (P, Q).

```lucas(k, P, Q)
```

Efficiently computes the kth terms in the Lucas U- and V-sequences U(P, Q) and V(P, Q). More explicitly, if

U0, U1, V0, V1 = 0, 1, 2, P

and we have the recursions

Un = P · Un-1 - Q · Un-2

Vn = P · Vn-1 - Q · Vn-2

then we compute Uk and Vk in O(ln(k)) arithmetic operations. If P2 ≠ 4·Q, then these sequences grow exponentially, so the number of bit operations is anywhere from O(k · ln(k)2 · ln(ln(k))) to O(k2) depending on how multiplication is handled. We recommend using MPZs when k > 100 or so. We divide by P2 - 4·Q at the end, so we handle separately the case where this is zero.

```binlinrecgen(P, Q, a, b)
```

The general binary linear recursion. Exactly like lucasgen, except we only compute one sequence, and we supply the seeds.

```binlinrec(k, P, Q, a, b)
```

The general binary linear recursion. Exactly like lucas, except we compute only one sequence, and we supply the seeds.

```linrecgen(a, b, m=None)
```

The general homogenous linear recursion: we generate in order the sequence defined by

xn+1 = ak · xn + ak-1 · xn-1 + … + a0 · xn-k,

where the initial values are [x0, …, xk] = b. If m is supplied, then we compute the sequence modulo m. The terms of this sequence usually grow exponentially, so computing a distant term incrementally by plucking it out of this generator takes O(n2) bit operations. Extractions of distant terms should therefore be done via linrec, which takes anywhere from O(n · ln(n)2 · ln(ln(n))) to O(n2) bit operations depending on how multiplication is handled.

```linrec(n, a, b, m=None)
```

The general homogeneous linear recursion. If m is supplied, terms are computed modulo m. We use matrix methods to efficiently compute the nth term of the recursion

xn+1 = ak · xn + ak-1 · xn-1 + … + a0 · xn-k,

where the initial values are [x0, …, xk] = b.

```legendre(a, p)
```

Legendre symbol (a | p): 1 if a is a quadratic residue mod p, -1 if it isn’t, and 0 if a ≡ 0 (mod p). Not meaningful if p isn’t prime.

```jacobi(a, n)
```

The Jacobi symbol (a | n).

```kronecker(a, n)
```

The Kronecker symbol (a | n). Note that this is the generalization of the Jacobi symbol, not the Dirac-delta analogue.

```fermat_prp(n, b)
```

Fermat’s primality test.

```sprp(n, b)
```

The strong probable primality test (aka single-round Miller-Rabin).

```mrab(n, basis)
```

Miller-Rabin probable primality test.

```miller(n)
```

Miller’s primality test. If the extended Riemann hypothesis (the one about Dirichlet L-functions) is true, then this test is deterministic.

```lprp(n, a, b)
```

Lucas probable primality test as described in Prime Numbers: A Computational Perspective by Crandall & Pomerance (2nd edition).

```lucasmod(k, P, Q, m)
```

Efficiently computed the kth terms of Lucas U- and V-sequences modulo m with parameters (P, Q). Currently just a helper function for slprp and xslprp. Will be upgraded to full status when the case gcd(D,m)!=1 is handled properly.

```slprp(n, a, b)
```

Strong lucas probable primality test as described on Wikipedia. Its false positives are a strict subset of those for lprp with the same parameters.

```xslprp(n, a)
```

Extra strong Lucas probable primality test as described on Wikipedia. Its false positives are a strict subset of those for slprp (and therefore lprp) with parameters (a, 1).

```bpsw(n)
```

The Baille-Pomerance-Selfridge-Wagstaff probable primality test. Infinitely many false positives are conjectured to exist, but none are known, and the test is known to be deterministic below 264.

```qfprp(n, a, b)
```

Quadratic Frobenius probable primality test as described in Prime Numbers: A Computational Perspective by Crandall & Pomerance (2nd edition).

```isprime(n, tb=(3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59))
```

The workhorse primality test. It is a BPSW primality test variant: we use the strong Lucas PRP test and preface the computation with trial division for speed. No composites are known to pass the test, though it is suspected that infinitely many will do so. There are definitely no such errors below 264. This function is mainly a streamlined version of bpsw.

```isprime_mersenne(p)
```

The Lucas-Lehmer test. Deterministically and efficiently checks whether the Mersenne number 2p-1 is prime.

```nextprime(n)
```

Smallest prime strictly greater than n.

```prevprime(n)
```

Largest prime strictly less than n, or None if no such prime exists.

```randprime(digits, base=10)
```

Returns a random prime with the specified number of digits when rendered in the specified base.

```sqrtmod_prime(a, p)
```

Finds x such that x2a (mod p). We assume that p is a prime and a is a quadratic residue modulo p. If any of these conditions is false, then the return value is meaningless.

```pollardrho_brent(n)
```

Factors integers using Brent’s variation of Pollard’s rho algorithm. If n is prime, we immediately return n; if not, we keep chugging until a nontrivial factor is found.

```pollard_pm1(n, B1=100, B2=1000)
```

Integer factoring function. Uses Pollard’s p-1 algorithm. Note that this is only efficient if the number to be factored has a prime factor p such that p-1’s largest prime factor is “small”.

```mlucas(v, a, n)
```

Helper function for williams_pp1. Multiplies along a Lucas sequence modulo n.

```williams_pp1(n)
```

Integer factoring function. Uses Williams’ p+1 algorithm, single-stage variant. Note that this is only efficient when the number to be factored has a prime factor p such that p+1’s largest prime factor is “small”.

```ecadd(p1, p2, p0, n)
```

Helper function for ecm. Adds two points on a Montgomery curve modulo n.

```ecdub(p, A, n)
```

Helper function for ecm. Doubles a point on a Montgomery curve modulo n.

```ecmul(m, p, A, n)
```

Helper function for ecm. Multiplies a point on Montgomery curve by an integer modulo n.

```ecm(n, B1=None, B2=None)
```

Integer factoring via elliptic curves. Uses Montgomery curves and the two-phase algorithm.

```modinv_mpqs(a, m)
```

Helper function for mpqs. Returns a modular inverse normalized to minimize absolute value.

```mpqs(n)
```

Factors an integer via the multiple-polynomial quadratic sieve. Most of this function is copied verbatim from https://codegolf.stackexchange.com/a/9088.

```multifactor(n, methods)
```

Integer factoring function. Uses several methods in parallel. Waits for one of them to return, kills the rest, and reports.

```primefac(n, trial=1000, rho=42000, primetest=isprime, methods=(pollardrho_brent,))
```

The workhorse integer factorizer. Generates the prime factors of the input. Factors that appear x times are yielded x times.

```factorint(n, trial=1000, rho=42000, primetest=isprime, methods=(pollardrho_brent,))
```

Compiles the output of primefac into a dictionary with primes as keys and multiplicities as values.

```factorsieve(stop)
```

Uses a sieve to compute the factorizations of all whole numbers strictly less than the input. This uses a lot of memory; if you aren’t after the factors directly, it’s usually better to write a dedicated function for whatever it is that you actually want.

```divisors(n)
```

Generates all natural numbers that evenly divide n. The output is not necessarily sorted.

```divisors_factored(n)
```

Generates the divisors of n, written as their prime factorizations in factorint format.

```divcount(n)
```

Counts the number of divisors of n.

```divsigma(n, x=1)
```

Sum of divisors of a natural number, raised to the xth power. The conventional notation for this in mathematical literature is σx(n), hence the name of this function.

```divcountsieve(stop)
```

Uses a sieve to compute the number of divisors of all whole numbers strictly less than the input.

```totient(n, k=1)
```

Jordan’s totient function: the number of k-tuples of positive integers all ≤ n that form a coprime (k+1)-tuple together with n. When k = 1, this is Euler’s totient: the number of numbers less than a number that are relatively prime to that number.

```totientsieve(n)
```

Uses a sieve to compute the totients up to (and including) n.

```totientsum(n)
```

Computes sum(totient(n) for n in range(1, n+1)) efficiently.

```mobius(n)
```

The Möbius function of n: 1 if n is squarefree with an even number of prime factors, -1 if n is squarefree with an odd number of prime factors, and 0 if n has a repeated prime factor.

```mobiussieve(stop)
```

Uses a sieve to compute the Möbius function of all whole numbers strictly less than the input.

```hensel_lift(x, a, p, e)
```

Hensel lifting for powers of odd primes. Helper function for sqrtmod_primepow.

```hensel_lift_2(a, e)
```

Hensel lifting for powers of 2. Helper function for sqrtmod_primepow.

```sqrtmod_primepow(a, p, n, toplevel=True)
```

Returns a sorted list of all square roots of a mod pn.

```sqrtmod(a, n)
```

Computes all square roots of a modulo n and returns them in a sorted list.

```PQa(P, Q, D)
```

Generates some sequences related to simple continued fractions of certain quadratic surds. A helper function for pell. Let P, Q, and D be integers such that Q ≠ 0, D > 0 is a nonsquare, and P2D (mod Q). We yield a sequence of tuples (Bi, Gi, Pi, Qi) where i is an index counting up from 0, x = (P+√D)/Q = [a0; a1, a2, …], (Pi+√D))/Qi is the ith complete quotient of x, and Bi is the denominator of the ith convergent to x. For full details, see https://www.jpr2718.org/pell.pdf.

```pell(D, N)
```

This function solves the generalized Pell equation: we find all non-negative integers (x, y) such that x2 - D · y2 = N. We have several cases:

Case 1: N = 0. We solve x2 = D · y2. (0,0) is always a solution.

Case 1a: If D is a nonsquare, then there are no further solutions.

Case 1b: If D is a square, then there are infinitely many solutions, parametrized by (t·√D, t).

Case 2: N ≠ 0 = D. We solve x2 = N.

Case 2a: If N is a nonsquare, then there are no solutions.

Case 2b: If N is a square, then there are infinitely many solutions, parametrized by (√N, t).

Case 3: N ≠ 0 > D. We solve x2 + |D| · y2 = N. The number of solutions will be finite.

Case 4: N ≠ 0 < D. We find lattice points on a hyperbola.

Case 4a: If D is a square, then the number of solutions will be at most finite. This case is solved by factoring.

Case 4b: If D is a nonsquare, then we run the PQa/LMM algorithms: we produce a set of primitive solutions; if this set is empty, there are no solutions; if this set has members, an ininite set of solutions can be produced by repeatedly composing them with the fundamental solution of x2 - D · y2 = 1.

References:

Input: D, N – integers

Output:

A 3-tuple.

If the number of solutions is finite, it is (None, z, None), where z is the sorted list of all solutions.

If the number of solutions is infinite and the equation is degenerate, it’s (gen, None, None), where gen yields all solutions.

If the number of solutions if infinite and the equation is nondegenerate, it is (gen, z, f), where z is the set of primitive solutions, represented as a sorted list, and f is the fundamental solution — i.e., f is the primitive solution of x2 - D · y2 = 1.

Note that we can check the infinitude of solutions by calling bool(pell(D,N)).

```simplepell(D, bail=inf)
```

Generates the positive solutions of x2 - D · y2 = 1. We use some optimizations specific to this case of the Pell equation that makes this more efficient than calling pell(D,1). Note that this function is not equivalent to calling pell(D,1): pell is concerned with the general equation, which may or may not have trivial solutions, and as such yields all non-negative solutions, whereas this function is concerned only with the simple Pell equation, which always has an infinite family of positive solutions generated from a single primitive solution and always has the trivial solution (1,0).

We yield only those solutions with xbail.

```carmichael(n)
```

The Carmichael lambda function: the smallest positive integer m such that am ≡ 1 (mod n) for all a such that gcd(a, n) = 1. Also called the reduced totient or least universal exponent.

```multord(b, n)
```

Computes the multiplicative order of b modulo n; i.e., finds the smallest k such that bk ≡ 1 (mod n).

```pythags_by_perimeter(p)
```

Generates all Pythagorean triples of a given perimeter by examining the perimeter’s factors.

```collatz(n)
```

Generates the Collatz sequence initiated by n. Stops after yielding 1.

```sqrtcfrac(n)
```

Computes the simple continued fraction for √n. We return the answer as (isqrt(n), [a,b,c,...,d]), where [a,b,c,...,d] is the minimal reptend.

```convergents(a)
```

Generates the convergents of a simple continued fraction.

```contfrac_rat(n, d)
```

Returns the simple continued fraction of the rational number n/d.

```ngonal(x, n)
```

Returns the xth n-gonal number. Indexing begins with 1 so that ngonal(1, n) = 1 for all applicable n.

```is_ngonal(p, n)
```

Checks whether p is an n-gonal number.

```partitions(n, parts=)
```

Computes with some semblance of efficiency the number of additive partitions of an integer. The parts argument is for memoization.

```partgen(n)
```

Generates partitions of integers in ascending order via an iterative algorithm. It is the fastest known algorithm as of June 2014.

```partconj(p)
```

Computes the conjugate of a partition.

```farey(n)
```

Generates the Farey sequence of maximum denominator n. Includes 0/1 and 1/1.

```fareyneighbors(n, p, q)
```

Returns the neighbors of p/q in the Farey sequence of maximum denominator n.

```ispractical(n)
```

Tests whether n is a practical number – i.e., whether every integer from 1 through n (inclusive) can be written as a sum of divisors of n. These are also called panarithmic numbers.

```hamming(ps, *ps2)
```

Generates all ps-smooth numbers, where ps is a list of primes.

```arithmeticderivative(n)
```

The arithmetic derivative of n: if n is prime, then n’ = 1; if -2 < n < 2, then n’ = 0; if n < 0, then n’ = -(-n)’; and (ab)’ = a’·b + b’·a.

```perfectpowers()
```

Generates the sequence of perfect powers without multiplicity.

```sqfrgen(ps)
```

Generates the squarefree products of the elements of ps.

```sqfrgenb(ps, b, k=0, m=1)
```

Generates the squarefree products of elements of ps. Does not yield anything > b. For best performance, ps should be sorted in decreasing order.

```stormer(ps, *ps2, abc=None)
```

Størmer’s theorem asserts that for any given set ps of prime numbers, there are only finitely many pairs of consecutive integers that are both ps-smooth; the theorem also gives an effective algorithm for finding them. We implement Lenstra’s improvement to this theorem.

The abc argument indicates that we are to assume an effective abc conjecture of the form c < abc · rad(a·b·c)abc. This enables major speedups. If abc is None, then we make no such assumptions.

```quadintroots(a, b, c)
```

Given integers a, b, and c, we return in a tuple all distinct integers x such that a·x2 + b·x + c = 0. This is primarily a helper function for cubicintrootsgiven and cubicintroots.

```cubicintrootsgiven(a, b, c, d, r)
```

Given integers a, b, c, d, and r such that a·r3 + b·r2 + c·r + d = 0, we find the cubic’s other two roots an return in a tuple all distinct integer roots (including r). This is primarily a helper function for cubicintroots.

```cubicintroots(a, b, c, d)
```

Given integers a, b, c, d, we return in a tuple all distinct integer roots of a·x3 + b·x2 + c·x + d. This is primarily a helper function for isprime_nm1.

```isprime_nm1(n, fac=None)
```

The n-1 primality test: given an odd integer n > 214 and a fully-factored integer F such that F divides n-1 and F > n0.3, we quickly determine without error whether n is prime. If the provided (partial) factorization of n-1 is insufficient, we compute the factorization ourselves.

```isprime_np1(n, fac=None)
```

The n+1 primality test: given an odd integer n > 214 and a fully-factored integer F such that F divides n+1 and F > n0.3, we quickly determine without error whether n is prime. If the provided (partial) factorization of n+1 is insufficient, we compute the factorization ourselves.

```mulparts(n, r=None, nfac=None)
```

Generates all ordered r-tuples of positive integers whose product is n. If r is None, then we generate all such tuples (regardless of size) that do not contain 1.

```dirconv(f, g, ffac=False, gfac=False)
```

This returns a function that is the Dirichlet convolution of f and g. When called with the keyword arguments at their default values, this is equivalent to the expression lambda n: sum(f(d) * g(n//d) for d in divisors(n)). If f or g needs to factor its argument, such as f == totient or g == mobius or something like that, then that lambda expression calls the factorizer a lot more than it needs to — we’re already factoring n, so instead of feeding those functions the integer forms of n’s factors, we can instead pass ffac=True or gfac=True when dirconv is called and we will call divisors_factored(n) instead and feed those factored divisors into f or g as appropriate. This optimization becomes more noticeable as the factoring becomes more difficult.

```dirichletinverse(f)
```

Computes the Dirichlet inverse of the input function f. Mathematically, functions f such that f(1) = 0 have no Dirichlet inverses due to a division by zero. This is reflected in this implementation by raising a ZeroDivisionError when attempting to evaluate dirichletinverse(f)(n) for any such f and any n. If f(1) is neither 1 nor -1, then dirichletinverse(f) will return Fraction objects (as imported from the fractions module).

```dirichletroot(f, r, val1)
```

Computes the rth Dirichlet root of the input function f whose value at 1 is val1. More precisely, let f be a function on the positive integers, let r be a positive integer, and let val1r = f(1). Then we return the unique function g such that f = g * g * … * g, where g appears r times and * represents Dirichlet convolution. The values returned will be Fraction objects (as imported from the fractions module).

```determinant(M)
```

Computes the determinant of a matrix via the Schur determinant identity.

```discriminant(coefs)
```

Computes the discriminant of a polynomial. The input list is ordered from lowest degree to highest — i.e., coefs[k] is the coefficient of the xk term.

### Dependencies

This package imports items from multiprocessing, itertools, fractions, random, math, and heapq. These are all in the Python standard library.

We attempt to import mpz from gmpy2, but this is purely for efficiency: if this import fails, we simply set mpz = int.

## Release historyRelease notifications 1.2.0 1.1.0

This version 1.0.8 1.0.7