Inclusion-Exclusion

// Count integers in [1..n] divisible by at least one of primes[]
// PIE over all subsets of primes
function countDivisible(n, primes) {
    const k = primes.length;
    let count = 0;
    for (let mask = 1; mask < (1 << k); mask++) {
        let lcm = 1, bits = 0;
        for (let i = 0; i < k; i++) {
            if (!((mask >> i) & 1)) continue;
            lcm = lcm / gcd(lcm, primes[i]) * primes[i];
            bits++;
        }
        count += (bits % 2 === 1 ? 1 : -1) * Math.floor(n / lcm);
    }
    return count;
}

// Derangements: permutations with no fixed points
// D(n) = n! * Σ_{k=0}^{n} (-1)^k / k!
// Or recursively: D(n) = (n-1)(D(n-1) + D(n-2))
function derangements(n) {
    if (n <= 1) return 1 - n;
    let [a, b] = [1, 0]; // D(0)=1, D(1)=0
    for (let i = 2; i <= n; i++) [a, b] = [b, (i - 1) * (a + b)];
    return b;
}

// Euler's totient: count integers 1..n coprime to n
// φ(n) = n * Π_{p|n} (1 - 1/p) = PIE over prime factors
function eulerTotient(n) {
    let phi = n;
    for (let p = 2; p * p <= n; p++) {
        if (n % p === 0) {
            while (n % p === 0) n /= p;
            phi -= phi / p;
        }
    }
    if (n > 1) phi -= phi / n;
    return phi;
}