Mathematical Algorithms

Why Should You Care About Mathematical Algorithms?

🔐

Cryptography & Security

RSA encryption, the foundation of internet security, relies on prime numbers and modular arithmetic. Every HTTPS connection uses these mathematical algorithms!

🎮

Game Development

Random number generation, procedural world generation, and loot drop calculations all use modular arithmetic and probability theory.

🤖

Machine Learning

Feature hashing, optimization algorithms, and neural network weight initialization depend on mathematical algorithms for efficiency.

💰

Finance & Economics

Compound interest calculations, risk assessment, portfolio optimization, and cryptocurrency mining all use these fundamental algorithms.

🧬

Bioinformatics

DNA sequence analysis, protein folding predictions, and genetic algorithms rely on combinatorics and number theory.

📊

Data Science

Hash functions for data structures, statistical sampling, and probabilistic algorithms all build on these mathematical foundations.

Level 1: The Basics (Start Here!)

Level 1

What is GCD? The Foundation of Number Theory!

GCD (Greatest Common Divisor) is like finding the biggest LEGO block that can build both numbers! It's used everywhere from simplifying fractions to optimizing computer graphics.

Interactive GCD Calculator

Watch the Euclidean algorithm in action!

Enter two numbers and click Calculate!

GCD Algorithm - The Magic Behind It 🪄

# The Euclidean Algorithm - 2000+ years old and still awesome!
def gcd(a, b):
    """
    Find the Greatest Common Divisor.
    Like finding the biggest piece that divides both pizzas equally!
    """
    while b != 0:
        # The magic: replace (a,b) with (b, a%b)
        # This is like cutting the bigger number by the smaller one
        remainder = a % b
        a = b
        b = remainder
    return a

# Example: GCD of 48 and 18
# Step 1: 48 = 18 × 2 + 12  (remainder: 12)
# Step 2: 18 = 12 × 1 + 6   (remainder: 6)
# Step 3: 12 = 6 × 2 + 0    (remainder: 0)
# Answer: 6!

result = gcd(48, 18)  # Returns 6
                                

Prime Numbers - The Atoms of Mathematics!

Prime numbers are like the atoms of math - they can't be broken down! Every number is either prime or made from primes.

Prime Number Checker

Is your number prime? Let's find out!

Enter a number to check!

Common Mistake #1: Checking All Numbers

# ❌ WRONG - Checking every number up to n
def is_prime_slow(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
                            

Why it's wrong: You only need to check up to √n! If n has a divisor larger than √n, it must also have one smaller than √n.

The Right Way

# ✅ CORRECT - Only check up to square root
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
                            

Level 2: Common Patterns

Level 2

Pattern 1: Modular Arithmetic - The Clock Math!

Modular arithmetic is like a clock - after 12 comes 1 again! It's used in hash tables, cryptography, and random number generation.

Modular Calculator

Explore modular arithmetic visually!

Enter values to calculate!

Fast Modular Exponentiation - Step by Step

1

Convert to binary: Express the exponent in binary form

2

Square and multiply: For each bit, square the result and multiply if bit is 1

3

Take modulo: After each operation to keep numbers small

Fast Modular Exponentiation

def power_mod(base, exp, mod):
    """
    Calculate (base^exp) % mod efficiently.
    Instead of calculating huge numbers, we keep them small!
    """
    result = 1
    base = base % mod
    
    while exp > 0:
        # If exp is odd, multiply base with result
        if exp % 2 == 1:
            result = (result * base) % mod
        
        # Now exp must be even
        exp = exp >> 1  # Divide by 2
        base = (base * base) % mod  # Square the base
    
    return result

# Example: 7^3 mod 5
# Normal way: 7^3 = 343, then 343 % 5 = 3
# Fast way: Never deal with 343, keep everything small!
result = power_mod(7, 3, 5)  # Returns 3
                                

Pattern 2: Sieve of Eratosthenes - Finding All Primes!

The Sieve is like crossing out all the composite numbers to find primes - super efficient!

Interactive Prime Sieve

Watch the sieve algorithm eliminate composite numbers!

Sieve of Eratosthenes Implementation

def sieve_of_eratosthenes(n):
    """Find all primes up to n - like a massive filter!"""
    # Start by assuming all numbers are prime
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # Mark all multiples of i as composite
            # Start from i² because smaller multiples already marked
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    # Collect all prime numbers
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

# Find all primes up to 30
primes = sieve_of_eratosthenes(30)
# Returns: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
                                

Practice Problems (From Easy to Hard)

Easy

Problem 1: LCM Calculator

Find the Least Common Multiple using GCD.

Think About It First!

Hint: LCM(a,b) × GCD(a,b) = a × b

Show Solution

def lcm(a, b):
    """LCM using the GCD relationship"""
    return abs(a * b) // gcd(a, b)

# Example: LCM(12, 18)
# GCD(12, 18) = 6
# LCM = (12 × 18) / 6 = 36
                                    

Medium

Problem 2: Count Primes

Count the number of prime numbers less than n.

Strategy Hint

Use the Sieve of Eratosthenes for efficiency!

Show Solution

def count_primes(n):
    """Count primes less than n"""
    if n <= 2:
        return 0
    
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n, i):
                is_prime[j] = False
    
    return sum(is_prime)
                                    

Hard

Problem 3: Modular Inverse

Find x such that (a × x) ≡ 1 (mod m) using Extended Euclidean Algorithm.

Advanced Strategy

Use Extended GCD to find Bézout coefficients!

Show Solution

def mod_inverse(a, m):
    """Find modular inverse using Extended Euclidean Algorithm"""
    def extended_gcd(a, b):
        if b == 0:
            return a, 1, 0
        gcd, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("Inverse doesn't exist")
    
    return (x % m + m) % m

# Example: Find inverse of 3 mod 11
# We want x such that 3x ≡ 1 (mod 11)
# Answer: x = 4, because 3 × 4 = 12 ≡ 1 (mod 11)
                                    

Level 3: Advanced Techniques

Advanced

Chinese Remainder Theorem

Solve systems of congruences - used in cryptography and parallel computing!

Chinese Remainder Theorem

def chinese_remainder_theorem(remainders, moduli):
    """
    Solve system of congruences:
    x ≡ remainders[0] (mod moduli[0])
    x ≡ remainders[1] (mod moduli[1])
    ...
    """
    total = 0
    prod = 1
    
    # Calculate product of all moduli
    for m in moduli:
        prod *= m
    
    for r, m in zip(remainders, moduli):
        p = prod // m
        # Find modular inverse of p modulo m
        total += r * mod_inverse(p, m) * p
    
    return total % prod

# Example: Find x where:
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)
# Answer: x = 23
                                

Miller-Rabin Primality Test

Probabilistic test for large primes - used in RSA key generation!

def miller_rabin(n, k=5):
    """
    Probabilistic primality test.
    Accuracy: 1 - (1/4)^k
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Write n-1 as d × 2^r
    r, d = 0, n - 1
    while d % 2 == 0:
        d //= 2
        r += 1
    
    # Witness loop
    import random
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    
    return True
                        

Catalan Numbers

Count valid parentheses, binary trees, and more!

Applications of Catalan Numbers

C₀ = 1: One way to arrange 0 pairs of parentheses
C₁ = 1: One way to arrange 1 pair: ()
C₂ = 2: Two ways: (()), ()()
C₃ = 5: Five ways: ((())), (()()), (())(), ()(()), ()()()
C₄ = 14, C₅ = 42, C₆ = 132...

Quick Reference Guide

Algorithm Complexity

Algorithm	Time Complexity	Space	When to Use
Euclidean GCD	O(log min(a,b))	O(1)	⚡ Finding GCD/LCM
Basic Prime Test	O(√n)	O(1)	⚡ Small numbers
Sieve of Eratosthenes	O(n log log n)	O(n)	🎯 All primes up to n
Miller-Rabin	O(k log³ n)	O(1)	🎯 Large primes
Fast Exponentiation	O(log exp)	O(1)	🎯 Large powers
Prime Factorization	O(√n)	O(log n)	📊 Factor decomposition
Combination nCr	O(min(r, n-r))	O(1)	📊 Counting problems

Essential Formulas

GCD × LCM = a × b
Fermat's Little: aᵖ⁻¹ ≡ 1 (mod p)
Euler's Theorem: aᶲ⁽ⁿ⁾ ≡ 1 (mod n)
Wilson's Theorem: (p-1)! ≡ -1 (mod p)
Catalan: Cₙ = C(2n,n)/(n+1)

Common Applications

✅ RSA Encryption
✅ Hash Tables
✅ Random Number Generation
✅ Digital Signatures
✅ Error Correction Codes
✅ Computer Graphics
✅ Blockchain & Crypto

Tips & Tricks

Use modular arithmetic to prevent overflow
6k±1 optimization for prime checking
Precompute factorials for combinations
Binary exponentiation for large powers
Segmented sieve for memory efficiency

💡 Pro Tips:

Always use modular arithmetic for large numbers to prevent overflow
Miller-Rabin is probabilistic but extremely reliable with k=5-10 rounds
For cryptography, use proven libraries instead of implementing your own
Precompute and cache results when dealing with repeated calculations
Remember: Every integer > 1 has a unique prime factorization!