Um loop é uma estrutura algébrica bastante simples. É um tuplo (L, +) onde L é um conjunto e + é um operador binário G x L → L . Isso é + leva dois elementos da G e retorna um novo elemento. O operador também é obrigado a preencher duas propriedades

• Cancelamento: Para cada a e b em G existe x e y únicos em G, de modo que

  a + x = b
  y + a = b
  

• Identidade: Existe um e em G tal que para cada a em G

  e + a = a
  a + e = a
  

Se você estiver familiarizado com o conceito de grupo, poderá notar que um loop é apenas um grupo que não possui uma propriedade associativa.

Os loops são bem simples, então as pessoas gostam de adicionar mais regras para criar novas estruturas mais interessantes. Uma tal estrutura é um circuito Moufang que é um circuito que também satisfaz a seguinte quatro identidades forall x , y e z em L

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 exemplo, a seguinte tabela Cayley representa um loop Moufang:

0  1  2  3
1  0  3  2
2  3  0  1
3  2  1  0

(Se você não estiver familiarizado, uma tabela Cayley é uma matriz quadrada M, onde M _{i, j} é igual a i + j . É uma maneira útil de representar operadores binários em um conjunto.)

Podemos mostrar que existe uma identidade facilmente 0. O cancelamento é um pouco mais difícil de mostrar, mas uma abordagem de força bruta produz essa tabela

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

Onde nossos elementos são as soluções para

a + x = b = x + a

(Você pode notar que esta tabela é idêntica à nossa tabela de Cayley. Vou deixar como um exercício para o leitor descobrir por que esse é o caso desse loop de Moufang)

Agora precisamos verificar as identidades de Moufang para nossa estrutura. Existem duas maneiras de fazer isso para a estrutura específica: a primeira maneira é perceber que ela é associativa e, portanto, preenche automaticamente os critérios; no entanto, isso não funcionará em geral, portanto, preferiríamos o resultado com força bruta. Existem 3 variáveis ​​livres, cada uma com um potencial de 4 valores em todas as expressões aqui. Isso significa que precisamos executar 7 * 4 ³ ou 448 cálculos. Vou deixar de fora os cálculos brutos, mas aqui está um Haskell que você pode usar para verificar isso .

Tarefa

Dado um número inteiro positivo n como entrada, o número de loops de Moufang que têm a ordem n . (a ordem de um grupo é o tamanho do conjunto)

Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

Aqui está o número de loops de Moufang para as primeiras 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

Python 3 , 475 410 bytes

Obrigado ao Mr.Xcoder por salvar alguns bytes!

Use a simetria da fórmula para salvar 65 bytes. Sim, é muita coisa.

from itertools import*
n=int(input())
P=permutations
R=[*range(n)]
u=[]
A=all
S=sorted
for T in P(P(R),n):u+=[T]*(A(A(R==S(x)for x in
t)and any([*x]==S(x)for x in t)and
A(t[z][t[x][t[z][y]]]==t[t[t[z][x]][z]][y]and
t[t[z][x]][t[y][z]]==t[t[z][t[x][y]]][z]for x in R
for y in R for z in R)for t
in(T,[*zip(*T)]))and A(A(1-A(p[T[i][j]]==U[p[i]][p[j]]for i in R
for j in R)for p in P(R))for U in u))
print(len(u))

Experimente online!

Alguns andpodem ser substituídos por *, resultam em menor número de unidades, mas ao custo de um tempo de execução significativamente mais lento:

Python 3 , ??? bytes

[TODO coloque código aqui]

(é claro que nem tudo *torna o programa significativamente mais lento, apenas alguns são críticos)

Ungolfed:

from itertools import *
n = 4 # int(input())
rangeN = list(range(n))

def is_moufang_loop(T):
    A = tuple(zip(*T))
    return all(
        all(sorted(x) == rangeN for x in t)
        and any(list(x) == sorted(x) for x in t)
        and all(
                T[z][T[x][T[z][y]]] == T[T[T[z][x]][z]][y]
            and T[T[z][x]][T[y][z]] == T[T[z][T[x][y]]][z]
            for x in rangeN for y in rangeN for z in rangeN)
        for t in (T, A)
    )

def isomorphic(loop1, loop2):
    for p in permutations(rangeN):
        if all(
            p[loop1[i][j]] == loop2[p[i]][p[j]]
            for i in rangeN
            for j in rangeN
        ): return True
    return False

unique_moufang_loops = []
for x in [
        cayley_table 
        for cayley_table in permutations(permutations(rangeN), n)
        if is_moufang_loop(cayley_table)
]:
    if all(not isomorphic(x, y) for y in unique_moufang_loops):
        unique_moufang_loops.append(x)

print(len(unique_moufang_loops))

Experimente online!

_{Nenhuma barra de rolagem ...}

Explicação:

O programa é bem simples.

• Cada possível "operador binário" é representado por uma tabela Cayley (indexação 0).
• A propriedade "identity" implica que existe uma etal que a e'th th linha e a eth th coluna são iguais a [0, 1, 2, ..., n-1], que é a mesma condição que

  a matriz Te sua transposição têm uma linha igual a [0, 1, 2, ..., n-1].

• A propriedade "cancelamento" é equivalente a

  Cada linha e cada coluna são uma permutação de [0, 1, 2, ..., n-1].

Então a parte

all(
        all(sorted(x) == rangeN for x in t) 
        and any(list(x) == sorted(x) for x in t) 
        for t in (T, A))

do código verifica isso. (para todas as linhas da matriz Te sua transposição A, a classificação é igual a rangeN, e existe uma linha em ambas Te Aque é igual a ela mesma sendo classificada)

As quatro condições de um loop Moufang são verificadas manualmente.

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)

No código, (a + b)é representado como T[a][b]. (devido à representação como tabela de Cayley). Use a comparação de igualdade de encadeamento Python para evitar duplicação de (z + x) + (y + z).

No entanto, porque a fórmula é simétrica:

Se mudarmos os operandos da +primeira fórmula, obteremos a segunda fórmula; e se trocarmos os operandos da +terceira fórmula, obteremos a quarta fórmula com xe o ylugar trocado.

Observe que a transposição da tabela Cayley é equivalente aos operadores binários que trocaram os operandos. ( x + y -> y + x)

Finalmente, todos os candidatos à mesa Cayley são escolhidos

permutations(permutations(rangeN), n) 

para que cada linha seja uma permutação de rangeN(qual é [0, 1, 2, ..., n-1]) e que haja nlinhas distintas.