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.
- 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.n_choose_r(n: int, r: int) int
Enumerate the number of ways to pick r elements from a collection of size n.
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 ret: int = 0
8 for dig in digs:
9 ret = ret * base + dig
10 return ret
11
12
13def lattice_paths(height: int, width: int) -> int:
14 """Enumerate the paths from one corner of a Manhattan grid to its opposite."""
15 return n_choose_r(height + width, height)
16
17
18def mul_inv(a: int, b: int) -> int:
19 """Multiplicative inverse for modulo numbers"""
20 if b == 1:
21 return 1
22 b0: int = b
23 x0: int = 0
24 x1: int = 1
25 while a > 1:
26 q: int = a // b
27 a, b = b, a % b
28 x0, x1 = x1 - q * x0, x0
29 if x1 < 0:
30 return x1 + b0
31 return x1
32
33
34def n_choose_r(n: int, r: int) -> int:
35 """Enumerate the number of ways to pick r elements from a collection of size n."""
36 return factorial(n) // factorial(r) // factorial(n - r)
37
38
39def triangle(n: int) -> int:
40 """Generates the sum of 1 thru n in O(1)."""
41 return n * (n + 1) // 2
42
43
44def quadratic(n: int, a: int, b: int) -> int:
45 return (n + a) * n + b
46
47
48def pentagonal(n: int) -> int:
49 return n * (3 * n - 1) // 2
50
51
52def is_pentagonal(x: int) -> int:
53 root = sqrt(24 * x + 1)
54 if not root.is_integer():
55 return False
56 iroot = int(root)
57 if (1 + iroot) % 6:
58 return False
59 return (1 + iroot) // 6
60
61
62def hexagonal(n: int) -> int:
63 return n * (2 * n - 1)