Introduction - What is a necklace?
A necklace is something that OEIS people are obsessed with. The OEIS challenge has like 5 necklace sequences.
A binary necklace of length
n is a loop with
n beads that are either
1. Two necklaces are the same if one can be rotated to become the other, and two reversible necklaces are the same if one can be rotated, reversed, or reversed and rotated to become the other.
A primitive necklace is one that cannot be expressed as more than one copy of a string of beads chained together. Note that the copies must be assembled all in the same order (no reversing) for a necklace to be considered non-primitive.
For example, let's take a look at this necklace:
0 1 1 0 1 1. It is not primitive because it can be expressed as
0 1 1 repeated twice.
0 1 0 1 1 is primitive.
0 1 1 0 is primitive because
0 1 and
1 0 are not considered the same string. This necklace is equivalent to
1 1 0 0 because it can be rotated left one bead to become this one, but not equivalent to
0 1 0 1 (which isn't primitive by the way).
Given an non-negative integer
n, return the number of distinct reversible primitive binary necklaces of length
n. Input and output as a single integer each.
The first few terms of this sequence are
1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110, 0-indexed.
This is OEIS A001371
Reference Implementation in Python 3 - quite slow