Using Math and Number Theory Patterns

1. Implementing Sieve of Eratosthenes

Example: Finding Primes up to 30

const sieveOfEratosthenes = (n) => {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }

  return primes;
};

console.log(sieveOfEratosthenes(30)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Step	Action	Description
1	`isPrime[0] = isPrime[1] = false`	Mark 0 and 1 as non-prime
2	`i = 2`	Start with the first prime number
3	`isPrime[i] = true`	Mark multiples of i as non-prime
4	`i++`	Move to next number
5	`Return primes`	Collect all numbers marked as prime

Note: The algorithm efficiently identifies all primes up to a given number n by iteratively marking the multiples of each prime starting from 2.

2. Solving Prime Factorization

Method	Description	Time Complexity	Space Complexity
Trial Division	Divide the number by primes starting from 2 until square root of n	`O(√n)`	`O(1)`
Pollard's Rho	Probabilistic algorithm for factoring large integers	`O(n^1/4)`	`O(1)`
Fermat's Factorization	Expresses number as difference of two squares	`O(√n)`	`O(1)`

Example: Trial Division Implementation

function primeFactorization(n) {
  const factors = [];
  let divisor = 2;

  while (divisor * divisor <= n) {
    while (n % divisor === 0) {
      factors.push(divisor);
      n /= divisor;
    }
    divisor++;
  }

  if (n > 1) factors.push(n);
  return factors;
}

console.log(primeFactorization(315)); // [3, 3, 5, 7]

Example: Fermat's Factorization

function fermatFactorization(n) {
  let a = Math.ceil(Math.sqrt(n));
  let b2 = a * a - n;

  while (!Number.isInteger(Math.sqrt(b2))) {
    a++;
    b2 = a * a - n;
  }

  const b = Math.sqrt(b2);
  return [a - b, a + b];
}

console.log(fermatFactorization(5959)); // [59, 101]

Note: Fermat's method works best when factors are close to each other.

3. Implementing Modular Exponentiation

Modular exponentiation is a mathematical operation that computes (a^b) mod m efficiently, even for very large numbers. It's commonly used in cryptography and number theory algorithms.

Parameter	Description	Values
base	The base of the exponentiation	Integer
exponent	The power to which the base is raised	Non-negative integer
modulus	The value to take the result modulo	Positive integer

Example: Fast Modular Exponentiation

function modPow(base, exponent, modulus) {
  if (modulus === 1) return 0;
  let result = 1;
  base = base % modulus;
  while (exponent > 0) {
    if (exponent % 2 === 1) {
      result = (result * base) % modulus;
    }
    exponent = Math.floor(exponent / 2);
    base = (base * base) % modulus;
  }
  return result;
}

// Example usage:
console.log(modPow(3, 4, 5)); // Output: 1 (since 3^4 = 81, and 81 mod 5 = 1)

Note: This implementation uses the binary exponentiation method, which reduces time complexity from O(b) to O(log b).

4. Implementing Extended Euclidean Algorithm

Property	Description	Notes
Extended Euclidean Algorithm	Computes GCD(a, b) and coefficients x, y such that ax + by = gcd(a, b)	Used in modular inverse and solving linear Diophantine equations

Example: Extended Euclidean Algorithm Implementation

function extendedGCD(a, b) {
  if (b === 0) {
    return { gcd: a, x: 1, y: 0 };
  }
  const { gcd, x: x1, y: y1 } = extendedGCD(b, a % b);
  const x = y1;
  const y = x1 - Math.floor(a / b) * y1;
  return { gcd, x, y };
}

// Example usage:
const result = extendedGCD(35, 15);
console.log(result); // { gcd: 5, x: -1, y: 2 }
// Verification: 35 * (-1) + 15 * 2 = 5

Note: The extended GCD algorithm is fundamental in cryptography, particularly for RSA key generation.

5. Finding Modular Inverse

Method	Description	Time Complexity	Notes
Extended Euclidean Algorithm	Finds integers x and y such that ax + by = gcd(a, b). For modular inverse, a and m must be coprime.	`O(log(min(a, m)))`	Used to compute modular inverse when `gcd(a, m) = 1`
Fermat's Little Theorem	If `p` is prime and `a` is not divisible by `p`, then `a^(p-1) ≡ 1 (mod p)`. Thus, `a^(-1) ≡ a^(p-2) (mod p)`.	`O(log m)`	Applicable only when modulus is prime
Binary Exponentiation	Used in Fermat's Little Theorem to compute large powers efficiently.	`O(log m)`	Optimized exponentiation for modular arithmetic

Example: Extended Euclidean Algorithm for Modular Inverse

function extendedGCD(a, b) {
  if (b === 0) return [a, 1, 0];
  const [gcd, x1, y1] = extendedGCD(b, a % b);
  const x = y1;
  const y = x1 - Math.floor(a / b) * y1;
  return [gcd, x, y];
}

function modInverse(a, m) {
  const [gcd, x] = extendedGCD(a % m, m);
  if (gcd !== 1) return null; // Modular inverse doesn't exist
  return (x % m + m) % m;
}

// Example usage:
console.log(modInverse(3, 11)); // Output: 4 (since 3 * 4 ≡ 1 (mod 11))

Example: Fermat's Little Theorem for Modular Inverse

function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

function modInverseFermat(a, m) {
  if (m <= 1 || gcd(a, m) !== 1) return null;
  return modPow(a, m - 2, m);
}

// Example usage:
console.log(modInverseFermat(3, 11)); // Output: 4 (since 3 * 4 ≡ 1 (mod 11))

Note: The modular inverse of a modulo m exists if and only if gcd(a, m) = 1.

6. Finding Euler's Totient Function

Euler's totient function, φ(n), counts the number of integers from 1 to n that are coprime to n. Two numbers are coprime if their greatest common divisor (GCD) is 1.

Property	Description	Formula
φ(n)	Number of integers k in the range 1 ≤ k ≤ n such that gcd(n, k) = 1	φ(n) = n × ∏_p\|n(1 - 1/p)

Example: Calculating φ(12)

To compute φ(12), we first find its prime factors: 2 and 3.

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function phi(n) {
  let result = n;
  for (let p = 2; p * p <= n; p++) {
    if (n % p === 0) {
      while (n % p === 0) n /= p;
      result -= result / p;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}

console.log(phi(12)); // Output: 4

The integers from 1 to 12 that are coprime to 12 are: 1, 5, 7, and 11. Hence, φ(12) = 4.

Note: For a prime p, φ(p) = p - 1. For n = p^k, where p is prime, φ(p^k) = p^k - p^k-1.

Key Properties of φ(n)

If n = p^k, where p is prime, then φ(n) = p^k - p^k-1.
If n = p × q, where p and q are distinct primes, then φ(n) = (p - 1)(q - 1).
For any n, the sum of φ(d) over all divisors d of n equals n.

7. Solving Linear Diophantine Equations

A Linear Diophantine Equation is an equation of the form:

ax + by = c

where a, b, and c are integers, and we seek integer solutions for x and y.

Such equations have integer solutions if and only if gcd(a, b) divides c.

Example: Solving ax + by = c

function extendedGCD(a, b) {
  if (b === 0) return [a, 1, 0];
  const [gcd, x1, y1] = extendedGCD(b, a % b);
  return [gcd, y1, x1 - Math.floor(a / b) * y1];
}

function solveLinearDiophantine(a, b, c) {
  const [gcd, x, y] = extendedGCD(a, b);
  if (c % gcd !== 0) return null; // No solution

  const multiplier = c / gcd;
  return [x * multiplier, y * multiplier];
}

// Example: 3x + 6y = 9
const result = solveLinearDiophantine(3, 6, 9);
console.log(result); // [1, 1]

Component	Description	Notes
ax + by = c	Standard form of the linear Diophantine equation	Integer coefficients and solutions required
gcd(a, b)	Greatest Common Divisor of `a` and `b`	Must divide `c` for integer solutions to exist
Extended Euclidean Algorithm	Used to find coefficients `x`, `y`	Computes `ax + by = gcd(a, b)`

Note: If gcd(a, b) does not divide c, there are no integer solutions.

Solution Steps

Compute gcd(a, b)
Check if it divides c
If yes, use Extended Euclidean Algorithm to find a particular solution
Scale the solution to match c

8. Finding Catalan Numbers

Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics. They appear in various counting problems, such as the number of valid parentheses expressions, binary trees, and triangulations of polygons.

Formula	Value	Description
C(n)	`C(n) = (2n)! / ((n+1)! * n!)`	Standard formula for the nth Catalan number
C(n) = (1 / (n+1)) * C(2n, n)	`C(n) = (1 / (n+1)) * (2n choose n)`	Alternative formula using binomial coefficients

Example: Computing the 5th Catalan Number

function catalan(n) {
  if (n <= 1) return 1;
  let catalan = new Array(n + 1);
  catalan[0] = catalan[1] = 1;
  for (let i = 2; i <= n; i++) {
    catalan[i] = 0;
    for (let j = 0; j < i; j++) {
      catalan[i] += catalan[j] * catalan[i - 1 - j];
    }
  }
  return catalan[n];
}

console.log(catalan(5)); // Output: 42

Example: Using Binomial Coefficients

function binomialCoeff(n, k) {
  let result = 1;
  for (let i = 0; i < k; i++) {
    result = result * (n - i) / (i + 1);
  }
  return Math.round(result);
}

function catalanBinomial(n) {
  let c = binomialCoeff(2 * n, n);
  return c / (n + 1);
}

console.log(catalanBinomial(5)); // Output: 42

Note: Catalan numbers grow very quickly. For example, C(10) = 16796, and C(20) = 6564120420.

9. Implementing Combinatorics

Example: Calculating Factorials

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Pattern	Description	Time Complexity	Space Complexity
Permutations	Arrangements of items where order matters	O(n!)	O(1)
Combinations	Selections of items where order doesn't matter	O(n! / (k!(n-k)!))	O(1)
Binomial Coefficient	Number of ways to choose k items from n items	O(k)	O(1)

Example: Generating Combinations

function combinations(arr, k) {
  if (k === 1) return arr.map(item => [item]);
  if (k === arr.length) return [arr];

  const result = [];
  for (let i = 0; i <= arr.length - k; i++) {
    const first = arr[i];
    const rest = combinations(arr.slice(i + 1), k - 1);
    for (const combo of rest) {
      result.push([first, ...combo]);
    }
  }
  return result;
}

console.log(combinations([1, 2, 3, 4], 2)); // [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Note: For large inputs, consider using iterative approaches or memoization to optimize performance.

Example: Using Binomial Coefficient

function binomialCoefficient(n, k) {
  if (k > n - k) k = n - k;
  let result = 1;
  for (let i = 0; i < k; i++) {
    result = result * (n - i) / (i + 1);
  }
  return Math.round(result);
}

console.log(binomialCoefficient(5, 2)); // 10

10. Solving Inclusion-Exclusion Principle

The inclusion-exclusion principle is a counting technique used to calculate the size of the union of multiple sets by accounting for overlaps between them.

Concept	Description	Formula
Basic Principle	For two sets A and B, the union size is \|A ∪ B\| = \|A\| + \|B\| - \|A ∩ B\|	`\|A ∪ B\| = \|A\| + \|B\| - \|A ∩ B\|`
Three Sets	For three sets A, B, and C: \|A ∪ B ∪ C\| = \|A\| + \|B\| + \|C\| - \|A ∩ B\| - \|A ∩ C\| - \|B ∩ C\| + \|A ∩ B ∩ C\|	`\|A ∪ B ∪ C\| = \|A\| + \|B\| + \|C\| - \|A ∩ B\| - \|A ∩ C\| - \|B ∩ C\| + \|A ∩ B ∩ C\|`

Example: Counting Numbers Divisible by 2, 3, or 5

Find how many numbers from 1 to 100 are divisible by at least one of 2, 3, or 5.

const total = 100;
const divBy2 = Math.floor(total / 2);
const divBy3 = Math.floor(total / 3);
const divBy5 = Math.floor(total / 5);
const divBy2And3 = Math.floor(total / 6);
const divBy2And5 = Math.floor(total / 10);
const divBy3And5 = Math.floor(total / 15);
const divBy2And3And5 = Math.floor(total / 30);

const inclusionExclusion = divBy2 + divBy3 + divBy5 - divBy2And3 - divBy2And5 - divBy3And5 + divBy2And3And5;
console.log(inclusionExclusion); // 73

Note: The inclusion-exclusion principle is useful for problems involving overlapping constraints or counting elements in unions of sets.

11. Implementing Chinese Remainder Theorem

Component	Description	Implementation
Chinese Remainder Theorem (CRT)	System of simultaneous congruences with pairwise coprime moduli	`Given: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ)`
Moduli	Pairwise coprime integers m₁, m₂, ..., mₙ	Ensure gcd(mᵢ, mⱼ) = 1 for i ≠ j
Solution	Unique solution modulo M = m₁ × m₂ × ... × mₙ	x = Σ(aᵢ × Mᵢ × yᵢ) mod M

Example: CRT Implementation in JavaScript

function extendedGCD(a, b) {
  if (b === 0) return [a, 1, 0];
  const [gcd, x1, y1] = extendedGCD(b, a % b);
  return [gcd, y1, x1 - Math.floor(a / b) * y1];
}

function modInverse(a, m) {
  const [gcd, x] = extendedGCD(a % m, m);
  return gcd === 1 ? ((x % m) + m) % m : null;
}

function chineseRemainder(a, m) {
  const M = m.reduce((acc, val) => acc * val);
  let x = 0;
  for (let i = 0; i < a.length; i++) {
    const Mi = M / m[i];
    const yi = modInverse(Mi, m[i]);
    x = (x + a[i] * Mi * yi) % M;
  }
  return x;
}

// Example usage:
const remainders = [2, 3, 1];
const moduli = [3, 5, 7];
console.log(chineseRemainder(remainders, moduli)); // Output: 53

Note: CRT is used in RSA encryption, cryptography, and solving systems of modular equations efficiently.

12. Implementing Fast Fourier Transform

The Fast Fourier Transform (FFT) is an efficient algorithm to compute the Discrete Fourier Transform (DFT) and its inverse. It reduces the time complexity from O(n²) to O(n log n).

Example: Basic FFT Implementation in JavaScript

function fft(signal) {
  const n = signal.length;
  if (n <= 1) return signal;

  const even = fft(signal.filter((_, i) => i % 2 === 0));
  const odd = fft(signal.filter((_, i) => i % 2 === 1));

  const result = new Array(n);
  for (let i = 0; i < n / 2; i++) {
    const angle = -2 * Math.PI * i / n;
    const w = Math.cos(angle) + Math.sin(angle) * 1j;
    result[i] = even[i] + w * odd[i];
    result[i + n / 2] = even[i] - w * odd[i];
  }
  return result;
}

// Example usage:
const input = [1, 0, 0, 0];
const output = fft(input);
console.log(output);

Component	Description	Notes
Time Complexity	`O(n log n)`	More efficient than DFT's O(n²)
Space Complexity	`O(n)`	Due to recursive calls and temporary arrays
Applications	`Signal Processing, Image Compression, Polynomial Multiplication`	Used in many domains requiring frequency domain analysis

Note: The FFT assumes the input size is a power of two. For other sizes, zero-padding or alternative algorithms like Bluestein's algorithm can be used.