Un bucle es una estructura algebraica bastante simple. Es una tupla (G, +) donde G es un conjunto y + es un operador binario G × G → G . Eso es + toma de dos elementos de G y devuelve un nuevo elemento. El operador también debe cumplir dos propiedades.
Cancelación: Por cada una y b en G existe único x y y en G tal que
a + x = b y + a = b
Identidad: hay una e en G tal que por cada a en G
e + a = a a + e = a
Si está familiarizado con el concepto de grupo, puede notar que un bucle es solo un grupo que no tiene una propiedad asociativa.
Los bucles son bastante simples, por lo que a la gente le gusta agregar más reglas para crear nuevas estructuras que sean más interesantes. Una de esas estructuras es un bucle de Moufang que es un bucle que también satisface las siguientes cuatro identidades para x , y y z en G
z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)
Por ejemplo, la siguiente tabla de Cayley representa un bucle Moufang:
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
(Si no está familiarizado, una tabla de Cayley es una matriz cuadrada M donde M i, j es igual a i + j . Es una forma práctica de representar operadores binarios en un conjunto).
Podemos demostrar que hay una identidad con bastante facilidad 0
. La cancelación es un poco más difícil de mostrar, pero un enfoque de fuerza bruta produce esta tabla
b a → 0 1 2 3
↓
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0
Donde nuestros elementos son las soluciones para
a + x = b = x + a
(Puede notar que esta tabla es idéntica a nuestra tabla de Cayley. Lo dejaré como ejercicio para que el lector descubra por qué este es el caso de este bucle de Moufang)
Ahora necesitamos verificar las identidades de Moufang para nuestra estructura. Hay dos formas de hacer esto para la estructura particular: la primera es darse cuenta de que es asociativa y, por lo tanto, cumple automáticamente con los criterios, sin embargo, esto no funcionará en general, por lo que preferiríamos forzar el resultado. Aquí hay 3 variables libres, cada una con un potencial de 4 valores en cada expresión. Esto significa que tenemos que realizar 7 * 4 3 o 448 cálculos. Dejaré de lado los cálculos en bruto, pero aquí hay algunos Haskell que puedes usar para verificar esto .
Tarea
Dado un número entero positivo n como entrada salida, el número de bucles Moufang que tienen orden n . (el orden de un grupo es el tamaño del conjunto)
Este es el código de golf, por lo que las respuestas se puntuarán en bytes con menos bytes mejor.
Casos de prueba
Aquí está el número de bucles Moufang para las primeras 71 entradas
1,1,1,2,1,2,1,5,2,2,1,6,1,2,1,19,1,5,1,6,2,2,1,20,2,2,5,5,1,4,1,122,1,2,1,18,1,2,2,19,1,7,1,5,2,2,1,103,2,5,1,6,1,17,2,17,2,2,1,18,1,2,4,4529,1,4,1,6,1,4,1
fuente
12
no lo es11
. Debería haberme dado cuenta de eso porque11
es el número primo.Respuestas:
Python 3 ,
475410 bytes¡Gracias a Mr.Xcoder por guardar algunos bytes!
Use la simetría de la fórmula para guardar 65 bytes. Si, eso es mucho.
Pruébalo en línea!
Algunos
and
pueden ser reemplazados por*
, resulta en un menor número de bytes pero a costa de un tiempo de ejecución significativamente más lento:Python 3 , ??? bytes
[TODO pone el código aquí]
(por supuesto, no todo
*
hace que el programa sea significativamente más lento, solo algunos de ellos son críticos)Sin golf:
Pruébalo en línea!
No hay barras de desplazamiento ...
Explicación:
El programa es bastante simple.
e
tal que tanto lae
'th fila como lae
' th columna son iguales[0, 1, 2, ..., n-1]
, que es la misma condición queEntonces, la parte
del código comprueba eso. (para todas las filas de la matriz
T
y su transposiciónA
, el orden es igual arangeN
, y existe una fila en ambosT
yA
eso equivale a que se ordene)Las cuatro condiciones de un bucle Moufang se verifican manualmente.
En el código,
(a + b)
se representa comoT[a][b]
. (debido a la representación como tabla de Cayley). Use la comparación de igualdad de encadenamiento de Python para evitar la duplicación de(z + x) + (y + z)
.Sin embargo, debido a que la fórmula es simétrica:
Si cambiamos los operandos de
+
en la primera fórmula, obtenemos la segunda fórmula; y si cambiamos los operandos de+
la tercera fórmula, obtenemos la fórmula de la cuarta conx
yy
lugar intercambiado.Tenga en cuenta que la transposición de la tabla Cayley es equivalente a los operadores binarios que tienen operandos intercambiados. (
x + y -> y + x
)Finalmente, todos los candidatos de la mesa de Cayley se seleccionan de
de modo que cada fila es una permutación de
rangeN
(que es[0, 1, 2, ..., n-1]
) y hayn
filas distintas.fuente