Module integer 

Core integer algorithms: GCD, LCM, modular arithmetic, root-finding, prime utilities, combinatorics, digit operations, and special numbers.

These are the fundamental building blocks used across number theory, combinatorics, and cryptography. Canonical home for all integer math — algorithms.rs re-exports from here.

Functions

bell_number

n-th Bell number: total partitions of a set of n elements.

bezout_coefficients

Bezout coefficients: returns (x, y) such that a*x + b*y = gcd(a, b).

binomial

Binomial coefficient n choose k. k > n returns 0.

catalan_number

n-th Catalan number: C(n) = (1/(n+1)) * C(2n, n).

checked_binomial

Binomial coefficient n choose k, returning None on overflow. k > n returns Some(0).

checked_factorial

n! as u128, returning None on overflow. Exact for n <= 34; returns None for n >= 35.

chinese_remainder

Chinese Remainder Theorem solver.

digit_count

Number of decimal digits in n.

digit_count_base

Number of digits of n in the given base (2-36). digit_count_base(0, 10) returns 1.

digit_sum

Sum of decimal digits of n.

divisor_count

Number of divisors: d(n) or tau(n).

divisor_sum

Sum of divisors: sigma(n).

double_factorial

Double factorial: n!! = n * (n-2) * (n-4) * ... * 1 (or 2).

euler_phi

Euler’s totient function phi(n): count of integers <= n that are coprime to n.

extended_gcd

Extended Euclidean algorithm: returns (g, x, y) such that a*x + b*y = g = gcd(|a|, |b|). g is always non-negative.

factorial

n! as u128 (exact up to n = 34; larger wraps silently).

fermat_number

n-th Fermat number: 2^(2^n) + 1.

fibonacci

n-th Fibonacci number (F_0 = 0, F_1 = 1) as u128 (exact up to n = 184).

from_base

Parse a string in the given base (2-36) to u64.

from_digits

Reconstruct a number from decimal digits (most significant first).

gcd

Greatest common divisor (Euclidean algorithm).

gcd_n

Greatest common divisor of n numbers.

is_abundant

Check if n is an abundant number: sum of proper divisors > n.

is_armstrong

Check if n is an Armstrong (Narcissistic) number: n = sum of its digits each raised to the power of the number of digits.

is_coprime

Check if a and b are coprime (gcd == 1).

is_cube

Check if n is a perfect cube: n = k^3 for some integer k.

is_deficient

Check if n is a deficient number: sum of proper divisors < n.

is_even

Returns true if n is even.

is_harshad

Check if n is a Harshad (Niven) number: divisible by sum of its digits.

is_odd

Returns true if n is odd.

is_palindrome

Check if n is a decimal palindrome.

is_palindrome_base

Check if n is a palindrome in the given base (2-36).

is_perfect_number

Check if n is a perfect number: sum of its proper divisors equals n.

is_perfect_power

Check if n is a perfect power: n = a^b for some a >= 2, b >= 2.

is_power_of

Check if n is a power of base.

is_power_of_two

true if n is a power of two (1, 2, 4, …). 0 is not.

is_prime

Trial-division primality test.

is_prime_miller_rabin

Miller-Rabin probabilistic primality test.

is_semiprime

Check if n is a semiprime: product of exactly two primes (not necessarily distinct).

is_smooth

Check if n is a smooth number: all prime factors <= bound.

is_square

Check if n is a perfect square.

is_squarefree

Check if n is squarefree: no repeated prime factors.

is_triangular

Check if n is a triangular number: n = k(k+1)/2.

isqrt

Integer square root: floor(sqrt(n)).

isqrt_rem

Integer square root with remainder: returns (floor(sqrt(n)), n - floor(sqrt(n))^2).

lcm

Least common multiple. Returns 0 for lcm(0, x).

lcm_n

Least common multiple of n numbers.

liouville

Liouville function lambda(n): (-1)^Omega(n) where Omega(n) = total number of prime factors with multiplicity.

log2_ceil

Ceiling integer log base 2: smallest k such that 2^k >= n. Returns 0 for n == 0.

log2_floor

Floor integer log base 2: largest k such that 2^k <= n. Returns 0 for n == 0.

log_base

Integer log base base: largest k such that base^k <= n. Returns 0 for n == 0 or base <= 1.

lucas_number

n-th Lucas number (L_0 = 2, L_1 = 1, L_n = L_{n-1} + L_{n-2}).

mersenne_number

n-th Mersenne number: 2^n - 1.

mobius

Mobius function mu(n):

mod_pow

Modular exponentiation: base^exp mod m (exponentiation by squaring).

modular_inverse

Modular multiplicative inverse: a^-1 mod m.

nearest_power_of_two

Nearest power of two to n. Ties round toward even (e.g. 3 -> 4, 5 -> 4).

next_power_of_two

Smallest power of two >= n. Returns 0 for n == 0.

next_prime

Next prime after n.

nth_prime

The n-th prime (1-indexed: 1st prime = 2).

partition_number

Number of integer partitions of n (partition function p(n)).

pascal_triangle

Generate the first n rows of Pascal’s triangle.

permutation_count

Number of permutations: P(n, r) = n! / (n - r)!.

popcount

Population count: number of set bits (1-bits) in n.

prev_prime

Largest prime strictly less than n.

prime_count

Count of primes <= n (prime-counting function pi(n)).

prime_factorization

Prime factorization of n: returns a vector of (prime, exponent) pairs.

prime_factors

Distinct prime factors of n.

primorial

Primorial: product of primes <= p.

radical

Radical (square-free kernel): product of distinct prime factors.

reverse_digits

Reverse the decimal digits of n.

reverse_digits_base

Reverse the digits of n in the given base (2-36).

segmented_sieve

Segmented sieve: all primes in [lo, hi].

sieve_of_eratosthenes

All primes <= n.

stirling_first

Unsigned Stirling numbers of the first kind: s(n, k).

stirling_second

Stirling numbers of the second kind: S(n, k).

subfactorial

Subfactorial (derangement number): !n = n! * sum(k=0..n) (-1)^k / k!.

sum_of_squares

Sum of squares without overflow: a^2 + b^2 computed in u128.

to_base

Convert n to a string in the given base (2-36).

to_digits

Convert n to a vector of decimal digits (most significant first).

tribonacci

n-th Tribonacci number (T_0 = 0, T_1 = 0, T_2 = 1, T_n = T_{n-1} + T_{n-2} + T_{n-3}).