Distintos collares binarios primitivos reversibles

8

Introducción - ¿Qué es un collar?

Un collar es algo con lo que la gente de OEIS está obsesionada. El desafío OEIS tiene como 5 secuencias de collar.

Un collar binario de longitud nes un lazo con ncuentas que son 0o 1. Dos collares son iguales si uno puede rotarse para convertirse en el otro, y dos collares reversibles son iguales si uno puede rotarse, invertirse o invertirse y rotarse para convertirse en el otro.

Un collar primitivo es uno que no se puede expresar como más de una copia de una cadena de cuentas encadenadas. Tenga en cuenta que las copias deben ensamblarse todas en el mismo orden (sin inversión) para que un collar se considere no primitivo.

Por ejemplo, vamos a echar un vistazo a este collar: 0 1 1 0 1 1. No es primitivo porque se puede expresar como 0 1 1repetido dos veces. 0 1 0 1 1es primitivo

0 1 1 0es primitiva debido 0 1y 1 0no se consideran la misma cadena. Este collar es equivalente a 1 1 0 0porque se puede girar hacia la izquierda una cuenta para convertirse en este, pero no es equivalente a 0 1 0 1(que por cierto no es primitivo).

Desafío

Dado un número entero no negativo n, devuelve el número de collares binarios primitivos reversibles distintos de longitud n. Entrada y salida como un solo entero cada uno.

Los primeros términos de esta secuencia son 1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 41100 indexados.

Esto es OEIS A001371

Implementación de referencia en Python 3 : bastante lenta

Hiperneutrino
fuente
44
Oh, lo entiendo: "primitivo" significa que no se puede girar parcialmente para obtener el collar original, ¿verdad?
ETHproductions
@ETHproductions ... Nunca lo pensé de esa manera. Sí, eso definitivamente es un entendimiento correcto. ¡Agradable!
HyperNeutrino
¿Por qué es 0 1 0 1primitivo? ¿No se 0 1repite dos veces?
Misha Lavrov
@MishaLavrov Gracias; Quise decir "no primitivo" whoops. Gracias
HyperNeutrino
ಠ_ಠ Estaba buscando una secuencia OEIS para publicar como un desafío y lo siguiente que veo es ... esto ... collares. ._.
totalmente humano

Respuestas:

6

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

Pruébalo en línea! Editar: Guardado 7 21 bytes gracias a @HalvardHummel.

Neil
fuente
157 bytes
Halvard Hummel
1
@HalvardHummel Gracias, no pude resolver cómo generar todas las permutaciones en un 1-liner.
Neil
5

JavaScript (ES6), 198 192 bytes

Tenía curiosidad por saber cómo sería una respuesta completamente matemática. Asi que aqui esta. Bastante largo pero muy 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

Manifestación

¿Cómo?

Esto se basa en las siguientes 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

Donde φ es la función totient de Euler y μ es la función de 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

NB: en la versión actual de golf, la segunda parte del código ahora está incrustada directamente dentro de M () . Pero eso hace que el código sea más difícil de leer.

Arnauld
fuente
4

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

Cómo funciona

  • {0,1}~Tuples~# encuentra todas las secuencias binarias de la longitud dada
  • U@Partition[#,L@#,1,1]&/@... encuentra todas las rotaciones posibles de cada una de ellas
  • MaximalBy[...,L]selecciona las entradas con las rotaciones más distintas; estos corresponden a los collares primitivos.
  • U[#,Reverse/@#]&/@... pone las rotaciones en cada entrada, y sus reversiones, en un orden canónico ...
  • (L=Length)@(U=Union)[...] ... para que podamos eliminar collares primitivos duplicados, y luego contar los elementos restantes.
  • 1~Max~... nos aseguramos de que el resultado sea al menos 1 para obtener el término cero correcto.

-2 bytes gracias a Jonathan Frech, y -2 gracias a mí aprendiendo de él

-15 bytes más de cambio MaximalBy y cambios relacionados

-10 de cambiar a Partition

Misha Lavrov
fuente
1
Creo que si reemplaza Lengthcon Ly define L=Length;, podría guardar un byte.
Jonathan Frech
1
126 bytes .
Jonathan Frech
125, ya que olvidé jugar al golf en una de las instancias de Longitud. ¡Gracias!
Misha Lavrov
Y ahora es 124, ya que aprendí de tu ejemplo y convertí otro ==1en a <2.
Misha Lavrov
3

Casco , 21 bytes

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

Pruébalo en línea! El enlace muestra resultados del 0 al 10.

Explicación

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

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

Explicación:

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>

Herman L
fuente