8
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Oh, I get it—"primitive" means it can't be partially rotated to get the original necklace, right? \$\endgroup\$ – ETHproductions Sep 24 '17 at 1:41
  • \$\begingroup\$ @ETHproductions ... I never thought of it that way. Yes, that is definitely a correct understanding. Nice! \$\endgroup\$ – HyperNeutrino Sep 24 '17 at 1:42
  • \$\begingroup\$ Why is 0 1 0 1 primitive? Isn't it 0 1 repeated twice? \$\endgroup\$ – Misha Lavrov Sep 24 '17 at 1:49
  • \$\begingroup\$ @MishaLavrov Thanks; I meant "not primitive" whoops. Thanks \$\endgroup\$ – HyperNeutrino Sep 24 '17 at 1:51
  • \$\begingroup\$ ಠ_ಠ I was looking for an OEIS sequence to post as a challenge and the next thing I see is... this... necklaces. ._. \$\endgroup\$ – totallyhuman Sep 24 '17 at 3:06
6
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 157 bytes \$\endgroup\$ – Halvard Hummel Sep 24 '17 at 10:15
  • 1
    \$\begingroup\$ @HalvardHummel Thanks, I couldn't work out how to generate all the permutations in a 1-liner. \$\endgroup\$ – Neil Sep 24 '17 at 10:21
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think if you replace Length with L and define L=Length;, you could save a byte. \$\endgroup\$ – Jonathan Frech Sep 24 '17 at 2:57
  • 1
    \$\begingroup\$ 126 bytes. \$\endgroup\$ – Jonathan Frech Sep 24 '17 at 3:04
  • \$\begingroup\$ 125, since I forgot to golf one of the instances of Length. Thanks! \$\endgroup\$ – Misha Lavrov Sep 24 '17 at 3:08
  • \$\begingroup\$ And now it's 124, since I have learned from your example and turned another ==1 into a <2. \$\endgroup\$ – Misha Lavrov Sep 24 '17 at 3:34
3
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Jelly, 25 bytes

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

Try it online!

Very inefficient.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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>

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.