math.py

View source code here on GitHub!

Includes

python.src.lib.math.from_digits(digs: Iterable[int], base: int = 10) → int

Reconstruct a number from a series of digits.

Runs in \(O(n)\) operations, where \(n\) is the number of digits. This means that it will take \(O(\log(m))\) where \(m\) is the original number.

python.src.lib.math.lattice_paths(height: int, width: int) → int

Enumerate the paths from one corner of a Manhattan grid to its opposite.

python.src.lib.math.mul_inv(a: int, b: int) → int

Multiplicative inverse for modulo numbers

Runs in \(O(\log(\min(a, b)))\) time. Given that this is typically used in the context of modulus math, we can usually assume \(a < b\), simplifying this to \(O(\log(a))\) time.

python.src.lib.math.n_choose_r(n: int, r: int) → int

Enumerate the number of ways to pick r elements from a collection of size n.

Runs in \(O(n)\) multiplications. Because of how Python works, numbers less than \(2^{64}\) will multiply in constant time. Larger numbers, however, will multiply in \(O(n^{1.585})\), giving an overall time complexity of \(O(n^{2.585})\).

python.src.lib.math.triangle(n: int) → int

Generates the sum of 1 thru n in O(1).

python.src.lib.math.quadratic(n: int, a: int, b: int) → int
python.src.lib.math.pentagonal(n: int) → int
python.src.lib.math.is_pentagonal(x: int) → int
python.src.lib.math.hexagonal(n: int) → int
 1from math import factorial, sqrt
 2from typing import Iterable
 3
 4
 5def from_digits(digs: Iterable[int], base: int = 10) -> int:
 6    """Reconstruct a number from a series of digits.
 7
 8    Runs in :math:`O(n)` operations, where :math:`n` is the number of digits. This means that it will take
 9    :math:`O(\\log(m))` where :math:`m` is the original number."""
10    ret: int = 0
11    for dig in digs:
12        ret = ret * base + dig
13    return ret
14
15
16def lattice_paths(height: int, width: int) -> int:
17    """Enumerate the paths from one corner of a Manhattan grid to its opposite."""
18    return n_choose_r(height + width, height)
19
20
21def mul_inv(a: int, b: int) -> int:
22    """Multiplicative inverse for modulo numbers
23
24    Runs in :math:`O(\\log(\\min(a, b)))` time. Given that this is typically used in the context of modulus math, we
25    can usually assume :math:`a < b`, simplifying this to :math:`O(\\log(a))` time."""
26    if b == 1:
27        return 1
28    b0: int = b
29    x0: int = 0
30    x1: int = 1
31    while a > 1:
32        q: int = a // b
33        a, b = b, a % b
34        x0, x1 = x1 - q * x0, x0
35    if x1 < 0:
36        return x1 + b0
37    return x1
38
39
40def n_choose_r(n: int, r: int) -> int:
41    """Enumerate the number of ways to pick r elements from a collection of size n.
42
43    Runs in :math:`O(n)` multiplications. Because of how Python works, numbers less than :math:`2^{64}` will multiply
44    in constant time. Larger numbers, however, will multiply in :math:`O(n^{1.585})`, giving an overall time complexity
45    of :math:`O(n^{2.585})`."""
46    return factorial(n) // factorial(r) // factorial(n - r)
47
48
49def triangle(n: int) -> int:
50    """Generates the sum of 1 thru n in O(1)."""
51    return n * (n + 1) // 2
52
53
54def quadratic(n: int, a: int, b: int) -> int:
55    return (n + a) * n + b
56
57
58def pentagonal(n: int) -> int:
59    return n * (3 * n - 1) // 2
60
61
62def is_pentagonal(x: int) -> int:
63    root = sqrt(24 * x + 1)
64    if not root.is_integer():
65        return False
66    iroot = int(root)
67    if (1 + iroot) % 6:
68        return False
69    return (1 + iroot) // 6
70
71
72def hexagonal(n: int) -> int:
73    return n * (2 * n - 1)