Math / Number Theory: Pattern Intuition Guide¶
"Mathematics is not about numbers, equations, computations, or algorithms: it is about understanding." β William Paul Thurston
The Nature of Math Patterns¶
Unlike sliding window or DP, math/number theory problems don't follow a single template. They're a toolbox β a collection of techniques you reach for when you recognize certain signals.
The challenge: recognizing which tool applies.
The Core Toolkit¶
1. GCD (Greatest Common Divisor)¶
Mental Model: What's the largest building block that both numbers are made of?
The GCD is the intersection of prime factors (taking minimum powers).
The Euclidean Algorithm: Instead of factoring, repeatedly replace the larger number with the remainder:
Key Property: gcd(a, b) = gcd(b, a % b)
2. Prime Numbers¶
Mental Model: Primes are the "atoms" of numbers β indivisible building blocks.
The Sieve: Instead of testing each number, cross out multiples: - 2 is prime β cross out 4, 6, 8, 10... - 3 is prime β cross out 9, 15, 21... - 4 is crossed out, skip - 5 is prime β cross out 25, 35...
What remains is prime.
3. Modular Arithmetic¶
Mental Model: Clock arithmetic. After 12, you go back to 1.
Key Properties: - (a + b) mod m = ((a mod m) + (b mod m)) mod m - (a Γ b) mod m = ((a mod m) Γ (b mod m)) mod m
This lets us keep numbers small during computation.
4. Base Conversion¶
Mental Model: Counting in different number systems.
Base 10 uses digits 0-9. Base 2 (binary) uses 0-1. Base 26 (Excel columns) uses A-Z.
The Algorithm: Repeatedly divide by base, collect remainders.
Pattern Recognition Signals¶
Signal: "Find GCD" or "Common divisor"¶
"What's the GCD of all elements?" "Reduce fraction to lowest terms"
Tool: Euclidean algorithm, chain GCD across elements.
Signal: "Count primes" or "Is prime"¶
"How many primes less than n?" "Check if n is prime"
Tool: Sieve of Eratosthenes for bulk, βn trial for single check.
Signal: "mod 10^9+7"¶
"Return answer modulo 10^9+7"
Tool: Modular arithmetic. Apply mod at every multiplication/addition.
Signal: "Convert to Excel column" or "Base conversion"¶
"Number to column title", "Bijective base-26"
Tool: Divide-and-remainder loop with base adjustment.
Common Gotchas¶
Gotcha 1: 1-indexed vs 0-indexed Bases¶
Excel columns: A=1, B=2, ..., Z=26 (1-indexed) Standard base-26: A=0, B=1, ..., Z=25 (0-indexed)
Fix: Subtract 1 before each division.
Gotcha 2: Integer Overflow in Modular Arithmetic¶
# Wrong: overflow before mod
result = (a * b) % MOD # May overflow if a*b > MAX_INT
# Right: mod each operand first
result = ((a % MOD) * (b % MOD)) % MOD
Gotcha 3: Sieve Optimization β Start from pΒ²¶
When sieving prime p, multiples < pΒ² are already marked by smaller primes. Starting from pΒ² saves significant work.
Gotcha 4: GCD with Zero¶
gcd(a, 0) = a β zero is divisible by everything.
This is the base case that terminates the Euclidean algorithm.
When Math Helps¶
Math patterns often provide dramatic speedups:
| Problem | Brute Force | With Math |
|---|---|---|
| GCD of array | O(n Γ max_val) | O(n Γ log(max)) |
| Count primes to n | O(nβn) | O(n log log n) |
| Large exponentiation | O(exp) | O(log exp) |
The key is recognizing when a problem has mathematical structure you can exploit.
Practice Progression¶
Master the math toolbox through this sequence:
- LC 1979 (GCD of Array) β Basic Euclidean algorithm
- LC 204 (Count Primes) β Sieve of Eratosthenes
- LC 168 (Excel Column Title) β Base conversion twist
- LC 50 (Pow(x,n)) β Binary exponentiation (extension)
The Unifying Principle¶
Math patterns are about recognizing structure.
Numbers aren't just values β they have properties: divisibility, primality, periodicity. When a problem involves these properties, mathematical techniques often provide elegant, efficient solutions.
"The tools are in your toolbox. The art is knowing when to use each one."