Number theory¶
At the bottom level of the package hierarchy are various helper functions which implement standard number-theoretic algorithms.
-
thompson.number_theory.
gcd
(a, b)[source]¶ Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive).
>>> gcd(12, 8) 4 >>> gcd(0, 50) 50 >>> gcd(7, 101) 1
-
thompson.number_theory.
extended_gcd
(a, b)[source]¶ From this exposition of the extended gcd algorithm. Computes \(d = \gcd(a, b)\) and returns a triple \((d, x, y)\) where \(d = ax + by\).
>>> extended_gcd(14, 33) (1, -7, 3) >>> extended_gcd(12, 32) (4, 3, -1)
-
thompson.number_theory.
lcm
(*args)[source]¶ Computes the least common multiple of the given args. If a single argument is provided, the least common multiple of its elements is computed.
>>> n = randint(1, 1000000) >>> lcm(n) == n True >>> lcm(2, 13) 26 >>> lcm(*range(1, 10)) #1, 2, ..., 9 2520 >>> lcm(range(1, 10)) #Don't have to unpack the arguments 2520
-
thompson.number_theory.
solve_linear_diophantine
(a, b, c)[source]¶ Solves the equation \(ax + by = c\) for integers \(x, y \in\mathbb{Z}\).
Return type: None
if no solution exists; otherwise a triple (base, inc, lcm) where- base is a single solution \((x_0, y_0)\);
- inc is a pair \((\delta x, \delta y)\) such that if \((x, y)\) is a solution, so is \((x, y) \pm (\delta x, \delta y)\); and
- lcm is the value of \(\operatorname{lcm}(a, b)\).
-
thompson.number_theory.
solve_linear_congruence
(a, b, n)[source]¶ Solves the congruence \(ax \equiv b \pmod n\).
Return type: a SolutionSet
representing all such solutions \(x\).>>> x = solve_linear_congruence(6, 12, 18) >>> print(x) {..., -1, 2, 5, 8, 11, 14, ...} >>> y = solve_linear_congruence(5, 7, 11) >>> print(y) {..., -3, 8, 19, 30, 41, 52, ...} >>> print(x & y) {..., -25, 8, 41, 74, 107, 140, ...}
-
thompson.number_theory.
divisors
(n, include_one=True)[source]¶ An iterator that yields the positive divisors \(d \mid n\).
Parameters: include_one (bool) – set to False to exlude \(d = 1\). >>> list(divisors(12)) [1, 2, 3, 4, 6, 12] >>> list(divisors(125, include_one=False)) [5, 25, 125]
-
thompson.number_theory.
prod
(iterable)[source]¶ Handy function for computing the product of an iterable collection of numbers. From Stack Overflow.
>>> prod(range(1, 5)) 24