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 n
es un lazo con n
cuentas que son 0
o 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 1
repetido dos veces. 0 1 0 1 1
es primitivo
0 1 1 0
es primitiva debido 0 1
y 1 0
no se consideran la misma cadena. Este collar es equivalente a 1 1 0 0
porque 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, 4110
0 indexados.
Esto es OEIS A001371
Implementación de referencia en Python 3 : bastante lenta
fuente
0 1 0 1
primitivo? ¿No se0 1
repite dos veces?Respuestas:
Python 2 ,
178171139137 bytesPruébalo en línea! Editar: Guardado
721 bytes gracias a @HalvardHummel.fuente
JavaScript (ES6),
198192 bytesTenía curiosidad por saber cómo sería una respuesta completamente matemática. Asi que aqui esta. Bastante largo pero muy rápido.
Manifestación
Mostrar fragmento de código
¿Cómo?
Esto se basa en las siguientes fórmulas:
Donde φ es la función totient de Euler y μ es la función de Möbius .
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.
fuente
Mathematica,
12812512410999 bytesCómo funciona
{0,1}~Tuples~#
encuentra todas las secuencias binarias de la longitud dadaU@Partition[#,L@#,1,1]&/@...
encuentra todas las rotaciones posibles de cada una de ellasMaximalBy[...,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
fuente
Length
conL
y defineL=Length;
, podría guardar un byte.==1
en a<2
.Casco , 21 bytes
Pruébalo en línea! El enlace muestra resultados del 0 al 10.
Explicación
fuente
Jalea , 25 bytes
Pruébalo en línea!
Muy ineficiente
fuente
Javascript (ES7), 180 bytes
Explicación:
fuente