Concepts18
Category
Floor Sum Formula
The floor sum computes S(n,m,a,b) = sum_{i=0}^{n-1} floor((a i + b)/m) efficiently in O(log(min(a,m))) time.
Generating Functions - EGF
Exponential generating functions (EGFs) encode a sequence (a_n) as A(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}, which naturally models labeled combinatorial objects.
Pólya Enumeration
Pólya Enumeration Theorem generalizes Burnside’s Lemma by turning counting under symmetry into a polynomial substitution problem.
Burnside's Lemma
Burnside's Lemma says the number of distinct objects up to a symmetry group equals the average number of objects fixed by each symmetry.
Partition Function
The partition function p(n) counts the number of ways to write n as a sum of positive integers where order does not matter.
Generating Functions - OGF
An ordinary generating function (OGF) encodes a sequence (a_n) as a formal power series A(x) = \sum_{n \ge 0} a_n x^n.
Stirling Numbers of First Kind
Stirling numbers of the first kind count permutations by their number of cycles and connect power polynomials to rising/falling factorials.
Stirling Numbers of Second Kind
Stirling numbers of the second kind S(n,k) count how many ways to split n labeled items into k non-empty, unlabeled groups.
Primitive Roots
A primitive root modulo n is a number g that cycles through all units modulo n when you repeatedly multiply by g, so its multiplicative order equals \(\varphi(n)\).
Discrete Logarithm
The discrete logarithm problem asks for x such that g^x ≡ h (mod p) in a multiplicative group modulo a prime p.
Pollard's Rho Factorization
Pollard's Rho is a randomized algorithm that finds a non-trivial factor of a composite integer by walking a pseudorandom sequence modulo n and extracting a factor with a gcd.
Quadratic Residues
A quadratic residue modulo an odd prime p is any a for which x^2 ≡ a (mod p) has a solution; exactly half of the nonzero classes are residues.