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\$
11
  • 4
    \$\begingroup\$ Oh, I get it—"primitive" means it can't be partially rotated to get the original necklace, right? \$\endgroup\$ Sep 24, 2017 at 1:41
  • \$\begingroup\$ @ETHproductions ... I never thought of it that way. Yes, that is definitely a correct understanding. Nice! \$\endgroup\$
    – hyper-neutrino
    Sep 24, 2017 at 1:42
  • \$\begingroup\$ Why is 0 1 0 1 primitive? Isn't it 0 1 repeated twice? \$\endgroup\$ Sep 24, 2017 at 1:49
  • \$\begingroup\$ @MishaLavrov Thanks; I meant "not primitive" whoops. Thanks \$\endgroup\$
    – hyper-neutrino
    Sep 24, 2017 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\$ Sep 24, 2017 at 3:06

6 Answers 6

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.

\$\endgroup\$
2
  • \$\begingroup\$ 157 bytes \$\endgroup\$ Sep 24, 2017 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, 2017 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.

\$\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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I think if you replace Length with L and define L=Length;, you could save a byte. \$\endgroup\$ Sep 24, 2017 at 2:57
  • 1
    \$\begingroup\$ 126 bytes. \$\endgroup\$ Sep 24, 2017 at 3:04
  • \$\begingroup\$ 125, since I forgot to golf one of the instances of Length. Thanks! \$\endgroup\$ Sep 24, 2017 at 3:08
  • \$\begingroup\$ And now it's 124, since I have learned from your example and turned another ==1 into a <2. \$\endgroup\$ Sep 24, 2017 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.
\$\endgroup\$
2
\$\begingroup\$

Jelly, 25 bytes

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

Try it online!

Very inefficient.

\$\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>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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