Module grscheller.boring_math.integer_math

Library of functions and classes of an integer pure math nature.

Functions

def comb(n: int, m: int, targetTop: int = 700, targetBot: int = 5) ‑> int

Implements C(n,m), the number of n items taken m at a time.

• geared to works efficiently for Python's arbitrary length integers
• default parameters geared to large values of n and m
• the defaults work reasonably well for smaller (human size) values
• for inner loops with smaller values, use targetTop = targetBot = 1
• or just use math.comb(n, m) instead
• raises ValueError if n < 0 or m < 0

def coprime(m: int, n: int) ‑> tuple[int, int]

Makes 2 integers coprime by dividing out their common factors.

• returns (0, 0) when n = m = 0
• returned coprimed values retain their original signs

def fibonacci(fib0: int, fib1: int) ‑> Iterator[int]

Returns iterator to Fibonacci sequence beginning fib0, fib1, …

def gcd(m: int, n: int) ‑> int

Uses Euclidean algorithm to compute the gcd of two integers.

• takes two integers, returns gcd > 0
• note that mathematically the gcd of 0 and 0 does not exist
• gcd(0, 0) = 1 a better choice than math.gcd(0, 0) = 0
• gcd(0, 0) = 1 eliminates lcm() & coprime() having to edge case test
• gcd()(0, 0) returning 1 instead of 0 more easily mathematically justified

def iSqrt(n: int) ‑> int

Integer square root of a non-negative integer.

• return the unique m such that m*m <= n < (m+1)*(m+1)
• raises: ValueError if n < 0

def isSqr(n: int) ‑> bool

Returns true if integer argument is a perfect square

def lcm(m: int, n: int) ‑> int

Finds the least common multiple (lcm) of two integers.

• takes two integers m and n
• returns lcm(m, n) > 0

def primes(start: int = 2, end_before: int = 100) ‑> Iterator[int]

Return a prime number iterator using the Sieve of Eratosthenes algorithm.