boofun.utils

Utility modules for boofun package.

boofun.utils.popcnt(x: int) → int

Return the population count of an integer.

boofun.utils.poppar(x: int) → int

Return the parity of the population count.

boofun.utils.over(n: int, k: int) → int

Safe binomial coefficient with bounds guarding.

boofun.utils.subsets(a: Sequence[int] | int, k: int | None = None) → Iterator[Tuple[int, ...]]

Yield subsets of sequence a (optionally fixed size).

boofun.utils.cartesian(seqs: Sequence[Sequence]) → Iterator[Tuple]

Yield cartesian product rows from sequences.

boofun.utils.num2bin_list(num: int, n_digits: int) → List[int]

Convert num to an n-digit binary list (MSB first).

boofun.utils.bits(i: int, n: int) → List[int]

Return n bits of i as a list (MSB first).

boofun.utils.tensor_product(A: ndarray | Sequence, B: ndarray | Sequence) → ndarray

Compute the Kronecker product of A and B.

boofun.utils.krawchouk(n: int, k: int, x: int) → int

Classical binary Krawchouk polynomial K_k(x; n).

boofun.utils.krawchouk2(n: int, k: int, x: int) → int

Legacy variant with (-2)^j weights (kept for completeness).

boofun.utils.hamming_distance(x: int, y: int) → int

Compute Hamming distance between two integers (number of differing bits).

boofun.utils.hamming_weight(x: int) → int

Alias for popcnt - number of 1 bits in x.

boofun.utils.generate_permutations(n: int) → Iterator[Tuple[int, ...]]

Generate all permutations of [0, 1, …, n-1].

boofun.utils.int_to_binary_tuple(x: int, n: int) → Tuple[int, ...]

Convert integer x to an n-bit binary tuple (LSB first).

Parameters:

• x – Integer to convert

• n – Number of bits

Returns:

Tuple of n bits, e.g., (0, 1, 1) for x=6 with n=3

boofun.utils.binary_tuple_to_int(bits: Sequence[int]) → int

Convert binary tuple (LSB first) to integer.

Parameters:

bits – Sequence of bits (0 or 1)

Returns:

Integer value

boofun.utils.gcd(a: int, b: int) → int

Greatest common divisor via math.gcd.

boofun.utils.invmod(a: int, m: int) → int

Modular inverse of a modulo m (raises ValueError if none).

boofun.utils.crt(moduli: Sequence[int], residues: Sequence[int]) → Tuple[int, int]

Chinese Remainder Theorem solution (value, modulus).

Raises:

ValueError – If no solution exists (e.g., incompatible moduli).

boofun.utils.is_prime(n: int) → bool

Deterministic primality for 64-bit n (SymPy-backed if available).

boofun.utils.prime_sieve(upto: int) → List[int]

Return primes <= upto via a simple Sieve of Eratosthenes.

boofun.utils.factor(n: int) → List[int]

Return prime factorization of n as a list of prime factors (with multiplicity).

Parameters:

n – Positive integer to factor

Returns:

List of prime factors in ascending order

Example

>>> factor(60)
[2, 2, 3, 5]
>>> factor(17)
[17]

boofun.utils.prime_factorization(n: int) → Dict[int, int]

Return prime factorization as a dictionary {prime: exponent}.

Parameters:

n – Positive integer to factor

Returns:

Dictionary mapping primes to their exponents

Example

>>> prime_factorization(60)
{2: 2, 3: 1, 5: 1}

boofun.utils.euler_phi(n: int) → int

Compute Euler’s totient function φ(n).

φ(n) = count of integers in [1, n] that are coprime to n.

Uses the formula: φ(n) = n * ∏_{p|n} (1 - 1/p)

Parameters:

n – Positive integer

Returns:

Euler’s totient of n

Example

>>> euler_phi(12)  # 1, 5, 7, 11 are coprime to 12
4

boofun.utils.totient(n: int) → int

Compute Euler’s totient function φ(n).

φ(n) = count of integers in [1, n] that are coprime to n.

Uses the formula: φ(n) = n * ∏_{p|n} (1 - 1/p)

Parameters:

n – Positive integer

Returns:

Euler’s totient of n

Example

>>> euler_phi(12)  # 1, 5, 7, 11 are coprime to 12
4

boofun.utils.binomial(n: int, k: int) → int

Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!).

Uses iterative computation to avoid large intermediate values.

Parameters:

• n – Total items

• k – Items to choose

Returns:

Number of ways to choose k items from n

Example

>>> binomial(5, 2)
10

boofun.utils.binomial_sum(n: int, k: int) → int

Compute sum of binomial coefficients: Σ_{i=0}^{k} C(n, i).

This is useful for counting functions of low degree.

Parameters:

• n – Total items

• k – Maximum selection size

Returns:

Sum of C(n,0) + C(n,1) + … + C(n,k)

Example

>>> binomial_sum(5, 2)  # C(5,0) + C(5,1) + C(5,2) = 1 + 5 + 10
16

boofun.utils.lcm(a: int, b: int) → int

Compute least common multiple of a and b.

Parameters:

• a – Integers

• b – Integers

Returns:

LCM(a, b)

boofun.utils.mobius(n: int) → int

Compute the Möbius function μ(n).

μ(n) = 0 if n has a squared prime factor μ(n) = (-1)^k if n is a product of k distinct primes μ(1) = 1

The Möbius function is important in combinatorics and number theory, particularly for Möbius inversion.

Parameters:

n – Positive integer

Returns:

μ(n) ∈ {-1, 0, 1}

Example

>>> mobius(1)
1
>>> mobius(6)  # 6 = 2 * 3, two distinct primes
1
>>> mobius(12)  # 12 = 2^2 * 3, has squared factor
0

boofun.utils.get_field(p: int = 2, m: int = 1) → GFField

Return a simple GF(p^m) descriptor.

class boofun.utils.GFField(p: int, m: int = 1)

Descriptor for GF(p^m).

p: int

m: int = 1

property order: int

element_type()

__init__(p: int, m: int = 1) → None

Modules

exceptions	Exception hierarchy for the BooFun library.
finite_fields	Optional finite field helpers (thin wrapper around galois if available).
logging	Logging utilities for the BooFun library.
math	Lightweight math helpers shared across BooFun modules.
number_theory	Number theory helpers with optional SymPy support.