Distinct Reversible Primitive Binary Necklaces

Question

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 0 or 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).

Challenge

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

Answer 1

Python 2, 178 171 139 137 bytes

lambda n:sum(1-any(i>int(b[j::-1]+b[:j:-1],2)or j*(i>=int(b[j:]+b[:j],2))for j in range(n))for i in range(2**n)for b in[bin(i+2**n)[3:]])

Try it online! Edit: Saved 7 21 bytes thanks to @HalvardHummel.

Answer 2

JavaScript (ES6), 198 192 bytes

I was curious to know what a fully mathematical answer would look like. So here it is. Quite long but very fast.

n=>(g=d=>d&&(n%d?0:(q=n/d,C=(a,b)=>b?C(b,a%b):a<2,M=n=>n%++k?k>n?(q%2+3)/4*(1<<q/2)+(R=d=>d&&(q%d?0:(P=k=>k--&&C(q/d,k)+P(k))(q/d)<<d)+R(d-1))(q)/q/2:M(n):n/k%k&&-M(n/k))(d,k=1))+g(d-1))(n)||1

Demo

let f =

n=>(g=d=>d&&(n%d?0:(q=n/d,C=(a,b)=>b?C(b,a%b):a<2,M=n=>n%++k?k>n?(q%2+3)/4*(1<<q/2)+(R=d=>d&&(q%d?0:(P=k=>k--&&C(q/d,k)+P(k))(q/d)<<d)+R(d-1))(q)/q/2:M(n):n/k%k&&-M(n/k))(d,k=1))+g(d-1))(n)||1

for(n = 0; n <= 30; n++) {
  console.log('a(' + n + ') = ' + f(n))
}

How?

This is based on the following formulas:

A000029(n) =
  (n % 2 + 3) / 4 * 2 ** floor(n / 2) +
  sum(φ(n / d) * 2 ** d, for d in divisors(n)) / (2 * n)

A001371(n) =
  1 if n = 0
  sum(μ(d) * A000029(n / d), for d in divisors(n)) if n > 0

Where φ is Euler's totient function and μ is Möbius function.

n => (g = d =>
  // if d = 0, stop the recursion of g()
  d && (
    // if d is not a divisor of n, ignore this iteration
    n % d ? 0 :
    (
      // define q = n / d, C = function that tests whether a and b are coprime,
      // M = Möbius function (requires k to be initialized to 1)
      q = n / d,
      C = (a, b) => b ? C(b, a % b) : a < 2,
      M = n => n % ++k ? k > n || M(n) : n / k % k && -M(n / k)
    )(d, k = 1) * ( // invoke M with d
      // first part of the formula for A000029
      (q % 2 + 3) / 4 * (1 << q / 2) +
      // 2nd part of the formula for A000029
      (R = d =>
        // if d = 0, stop the recursion of R()
        d && (
          // if d is not a divisor of q, ignore this iteration
          q % d ? 0 :
          // compute phi(q / d) * 2 ** d
          (P = k => k-- && C(Q, k) + P(k))(Q = q / d) << d
        // recursive call to R()
        ) + R(d - 1)
      )(q) / q / 2 // invoke R with q, and divide the result by q * 2
    )
  // recursive call to g()
  ) + g(d - 1)
)(n) || 1

NB: In the current golfed version, the 2nd part of the code is now directly embedded inside M(). But that makes the code harder to read.

Answer 3

Mathematica, 128 125 124 109 99 bytes

1~Max~(L=Length)@(U=Union)[U[#,Reverse/@#]&/@MaximalBy[U@Partition[#,L@#,1,1]&/@{0,1}~Tuples~#,L]]&

How it works

• {0,1}~Tuples~# finds all binary sequences of the given length
• U@Partition[#,L@#,1,1]&/@... finds all possible rotations of each one of them
• MaximalBy[...,L] picks out the entries with the most distinct rotations; these correspond to the primitive necklaces.
• U[#,Reverse/@#]&/@... puts the rotations in each entry, and their reversals, into a canonical order...
• (L=Length)@(U=Union)[...] ...so that we can delete duplicate primitive necklaces, and then count the elements remaining.
• 1~Max~... we make sure the result is at least 1 to get the zeroth term right.

---

-2 bytes thanks to Jonathan Frech, and -2 thanks to me learning from him

-15 more bytes from switching to MaximalBy and related changes

-10 from switching to Partition

Answer 4

Husk, 21 bytes

Ṡ#▲mLüOmȯṁSe↔U¡ṙ1ΠRḋ2

Try it online! The link shows results from 0 to 10.

Explanation

Ṡ#▲mLüOmȯṁSe↔U¡ṙ1ΠRḋ2  Implicit input, say n=4.
                  Rḋ2  The list [1,0] repeated n times: [[1,0],[1,0],[1,0],[1,0]]
                 Π     Cartesian product: [[1,1,1,1],[0,1,1,1],[1,0,1,1],...,[0,0,0,0]]
       mȯ              For each list, say x=[0,1,0,0]:
              ¡ṙ1        Iterate rotation by one step: [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0],[0,1,0,0],...
             U           Take prefix of unique values: [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]
         ṁSe↔            After each element, insert its reversal: [[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1],[0,0,0,1],[1,0,0,0],[0,0,1,0],[0,1,0,0]]
     üO                Remove duplicates with respect to sorting.
   mL                  Get length of each list of lists.
Ṡ#▲                    Count the number of maximal lengths.

Answer 5

Jelly, 25 bytes

2ḶṗµṙJ;U$ṢḢµ€QµsJṖE€ẸṆµ€S

Try it online!

Very inefficient.

Answer 6

Javascript (ES7), 180 bytes

n=>[...Array(2**n)].filter((_,m)=>![...m=m.toString(2).padStart(n,0)].some(_=>s[m=m.replace(/(.)(.*)/,"$2$1")]|s[[...m].reverse().join``])&!/^(.+)\1+$/.test(m)&(s[m]=1),s=[]).length

Explanation:

n=>[...Array(2**n)].filter((_,m)=>(     // For every number m from 0 to 2^n-1
    m=m.toString(2).padStart(n,0),      // Take the binary representation (padded)

    ![...m].some(_=>(                   // Repeat once for every digit in m
        m=m.replace(/(.)(.*)/,"$2$1"),  // Rotate m one step
        s[m]|s[[...m].reverse().join``] // Search for m and the reverse of m in the
    ))                                  // lookup table

    &!/^(.+)\1+$/.test(m)               // Test if m is primitive
    &(s[m]=1)                           // Add m to the lookup table

),s=[]).length                          // Get the length of the list of numbers that
                                        // satisfy the above conditions

f=n=>[...Array(2**n)].filter((_,m)=>![...m=m.toString(2).padStart(n,0)].some(_=>s[m=m.replace(/(.)(.*)/,"$2$1")]|s[[...m].reverse().join``])&!/^(.+)\1+$/.test(m)&(s[m]=1),s=[]).length

<input id=i type=number value=5/><button onclick="o.innerText=f(i.value)">Test</button><br><pre id=o></pre>