Pattern #24 — Mathematical Patterns 🔢
Pattern #24 — Mathematical Patterns 🔢
The final pattern! A small toolkit of number-theory tricks that show up again and again. You don't need to be a math genius — just know these handful of recipes.
1. GCD — Greatest Common Divisor
The biggest number that divides two numbers evenly.
GCD(12, 18) = 6.
The Euclidean Algorithm (2000+ years old, still perfect):
"Keep replacing the bigger number with the remainder until
one becomes 0. The other is the GCD."
GCD(48, 18):
48 % 18 = 12 → GCD(18, 12)
18 % 12 = 6 → GCD(12, 6)
12 % 6 = 0 → GCD(6, 0) = 6 ✅
function gcd(a, b) {
while (b) [a, b] = [b, a % b];
return a;
}
💡 LCM (least common multiple) = a * b / gcd(a, b)
2. Prime Numbers & the Sieve of Eratosthenes
A PRIME has exactly two divisors: 1 and itself (2,3,5,7,11...).
Check ONE number is prime → only test up to √n:
function isPrime(n) {
if (n < 2) return false;
for (let i = 2; i * i <= n; i++) // i*i ≤ n (up to √n)
if (n % i === 0) return false;
return true;
}
Find ALL primes up to n → the SIEVE (cross out multiples):
────────────────────────────────────────────────────────
2 3 4̶ 5 6̶ 7 8̶ 9̶ 10̶ 11 ...
Start at 2, cross out 4,6,8,10... Then 3, cross out 6,9,12...
Whatever's left uncrossed is prime.
function sieve(n) {
const isP = new Array(n + 1).fill(true);
isP[0] = isP[1] = false;
for (let i = 2; i * i <= n; i++)
if (isP[i])
for (let j = i * i; j <= n; j += i) isP[j] = false; // cross out
return isP;
}
3. Fast Exponentiation (Power in O(log n))
Computing 2^10 the slow way = multiply 2 ten times.
FAST way: use the fact that x^n = (x^(n/2))², halving each step.
2^10 = (2^5)²
2^5 = 2 · (2^2)²
2^2 = (2^1)²
→ only ~log(n) multiplications instead of n. 🚀
function fastPow(x, n) {
let result = 1;
while (n > 0) {
if (n & 1) result *= x; // if this bit is set, multiply
x *= x; // square the base
n >>= 1; // move to next bit
}
return result;
}
4. Other Handy Number Tricks
• Sum of 1..n = n * (n + 1) / 2 (no loop needed!) • Reverse a number = pop last digit (n%10), build up (r*10+d) • Count digits = Math.floor(Math.log10(n)) + 1 • Is it a palindrome number? reverse it and compare • Factorial = n! = n × (n-1)! (watch for overflow)
5. 🔍 How to SPOT This Pattern
Use Math Patterns when you see: ✅ "GCD", "LCM", "divisible", "common factor" ✅ "prime", "count primes", "prime factors" ✅ "power", "x^n", "modular exponentiation" ✅ "reverse a number", "palindrome number", "digit sum" ✅ "how many ways" that reduces to a formula (combinatorics)
6. Practice Problems
⭐ core • Count Primes • Greatest Common Divisor of Strings • Power of Three / Four • Reverse Integer • Palindrome Number ⭐⭐ Medium • Pow(x, n) — fast exponentiation • Excel Sheet Column Number • Happy Number • Ugly Number
7. ⚠️ Common Mistake
❌ Checking primality by testing ALL numbers up to n. Only test
up to √n — a divisor bigger than √n always has a partner
smaller than √n.
❌ Integer OVERFLOW with factorials/powers. Watch limits, and
use modular arithmetic when the problem says "answer mod 1e9+7".
Key Takeaway
Math Patterns = a small toolkit: Euclid's GCD, the Sieve for primes, fast exponentiation for powers, and digit tricks. You don't invent these in the room — you recognize the problem and apply the known recipe.
🎉 You Finished All 24 Patterns!
┌─────────────────────────────────────────────────────────────┐ │ │ │ You now have the COMPLETE pattern toolkit. From here: │ │ │ │ 1. Re-read the "How to Recognize" table in the index — │ │ that's your problem-solving compass. 🧭 │ │ │ │ 2. When you see a new problem, DON'T panic. Ask: │ │ "which pattern do the clue words point to?" │ │ │ │ 3. Solve 3–5 problems per pattern. Quality over quantity. │ │ │ │ 4. Re-draw the diagrams from memory. If you can teach it, │ │ you know it. │ │ │ │ Remember: you're not memorizing 500 problems. You're │ │ recognizing 24 patterns. That's the easy way. 🚀 │ │ │ └─────────────────────────────────────────────────────────────┘
Congratulations — and happy coding! You've got this. 🙏
Post a Comment