Burnside's Lemma

// Count distinct necklaces with n beads and k colors (rotations only)
function countNecklaces(n, k) {
    const gcd = (a, b) => b ? gcd(b, a % b) : a;
    let total = 0;
    for (let i = 0; i < n; i++) {
        // Rotation by i: fixed colorings = k^gcd(i,n)
        total += Math.pow(k, gcd(i, n));
    }
    return total / n;
}

// Count distinct bracelets (rotations AND reflections)
function countBracelets(n, k) {
    const gcd = (a, b) => b ? gcd(b, a % b) : a;
    let total = 0;
    // Rotations (n symmetries)
    for (let i = 0; i < n; i++) total += Math.pow(k, gcd(i, n));
    // Reflections (n symmetries)
    if (n % 2 === 0) {
        // n/2 reflections through pairs of opposite beads: each fixes k^(n/2+1) colorings
        // n/2 reflections through midpoints of opposite edges: each fixes k^(n/2) colorings
        total += (n / 2) * Math.pow(k, n / 2 + 1);
        total += (n / 2) * Math.pow(k, n / 2);
    } else {
        // n reflections each through one bead and midpoint of opposite edge
        total += n * Math.pow(k, (n + 1) / 2);
    }
    return total / (2 * n);
}