Count Necklaces

Problem

Count the distinct necklaces of length n using k colours, where two necklaces are the same when one is a rotation of the other.

Apply Burnside's lemma: average the number of colourings fixed by each rotation, where a rotation by i positions fixes k to the power gcd(i, n) colourings. Assume n >= 1 and k >= 1.

Hint

The sum over rotations is always divisible by n, so integer division is exact.

Test cases

case 1

in: [3,2]

expected: 4

case 2

in: [4,2]

expected: 6

case 3

in: [2,3]

expected: 6

case 4

in: [1,5]

expected: 5

case 5

in: [6,2]

expected: 14

Starter codePython

def count_necklaces(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor