Introdução - O que é um colar?

Um colar é algo pelo qual as pessoas da OEIS são obcecadas. O desafio OEIS tem 5 sequências de colar.

Um colar binário de comprimento né um laço com ncontas que são 0ou 1. Dois colares são iguais se um pode ser girado para se tornar o outro, e dois colares reversíveis são os mesmos se um pode ser girado, revertido ou invertido e girado para se tornar o outro.

Um colar primitivo é aquele que não pode ser expresso como mais de uma cópia de um colar de contas encadeadas. Observe que as cópias devem ser montadas todas na mesma ordem (sem reversão) para que um colar seja considerado não primitivo.

Por exemplo, vamos dar uma olhada neste colar: 0 1 1 0 1 1. Não é primitivo porque pode ser expresso como 0 1 1repetido duas vezes. 0 1 0 1 1é primitivo.

0 1 1 0é primitivo porque 0 1e 1 0não é considerado a mesma sequência. Este colar é equivalente a, 1 1 0 0porque pode ser girado à esquerda de uma conta para se tornar essa, mas não é equivalente a 0 1 0 1(que não é primitivo a propósito).

Desafio

Dado um número inteiro não negativo n, retorne o número de colares binários primitivos reversíveis distintos de comprimento n. Entrada e saída como um único número inteiro cada.

Os primeiros termos dessa sequência são 1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110indexados em 0.

Este é o OEIS A001371

Implementação de referência em Python 3 - bastante lenta

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:]])

Experimente online! Edit: Salvo 7 21 bytes graças a @HalvardHummel.

JavaScript (ES6), 198 192 bytes

Eu estava curioso para saber como seria uma resposta totalmente matemática. Então aqui está. Muito longo, mas muito rápido.

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))
}

Quão?

Isso se baseia nas seguintes fórmulas:

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

Onde φ é a função totiente de Euler e μ é a função Möbius .

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

Nota: Na versão atual, a segunda parte do código está agora diretamente incorporada em M () . Mas isso dificulta a leitura do código.

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]]&

Como funciona

• {0,1}~Tuples~# localiza todas as seqüências binárias do comprimento especificado
• U@Partition[#,L@#,1,1]&/@... encontra todas as rotações possíveis de cada uma delas
• MaximalBy[...,L]seleciona as entradas com as rotações mais distintas; estes correspondem aos colares primitivos.
• U[#,Reverse/@#]&/@... coloca as rotações em cada entrada e suas reversões em uma ordem canônica ...
• (L=Length)@(U=Union)[...] ... para que possamos excluir colares primitivos duplicados e contar os elementos restantes.
• 1~Max~... garantimos que o resultado seja pelo menos 1 para acertar o termo zero.

-2 bytes graças a Jonathan Frech e -2 graças a mim aprendendo com ele

-15 mais bytes da mudança para MaximalBy e alterações relacionadas

-10 da mudança para Partition

Casca , 21 bytes

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

Experimente online! O link mostra resultados de 0 a 10.

Explicação

Ṡ#▲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.

Gelatina , 25 bytes

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

Experimente online!

Muito ineficiente.

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

Explicação:

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>