Une boucle est une structure algébrique assez simple. Il est un tuple (G, +) où G est un ensemble et + est un opérateur binaire G × G → G . C'est-à-dire + prend deux éléments de G et retourne un nouvel élément. L'opérateur doit également remplir deux propriétés

• Annulation: pour chaque a et b dans G, il existe des x et y uniques dans G tels que

  a + x = b
  y + a = b
  

• Identité: il y a un e dans G tel que pour chaque a dans G

  e + a = a
  a + e = a
  

Si vous connaissez le concept de groupe, vous remarquerez peut-être qu'une boucle n'est qu'un groupe qui n'a pas de propriété associative.

Les boucles sont assez simples, donc les gens aiment ajouter plus de règles pour rendre les nouvelles structures plus intéressantes. Une telle structure est une boucle de Moufang qui est une boucle qui satisfait également les quatre identités suivantes pour tous les x , y et z dans 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)

Par exemple, le tableau Cayley suivant représente une boucle de Moufang:

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

(Si vous n'êtes pas familier, une table Cayley est une matrice carrée M où M _{i, j} est égal à i + j . C'est un moyen pratique pour représenter les opérateurs binaires sur un ensemble.)

On peut montrer qu'il y a une identité assez facilement 0. L'annulation est un peu plus difficile à montrer, mais une approche par force brute donne ce tableau

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

Où nos éléments sont les solutions pour

a + x = b = x + a

(Vous remarquerez peut-être que ce tableau est identique à notre tableau Cayley. Je vais laisser un exercice au lecteur pour comprendre pourquoi c'est le cas pour cette boucle Moufang)

Maintenant, nous devons vérifier les identités Moufang pour notre structure. Il y a deux façons de le faire pour la structure particulière, la première consiste à réaliser qu'elle est associative et remplit donc automatiquement les critères, mais cela ne fonctionnera pas en général, nous préférons donc le résultat brutalement. Il y a 3 variables libres chacune avec un potentiel de 4 valeurs dans chaque expression ici. Cela signifie que nous devons effectuer 7 * 4 ³ ou 448 calculs. Je laisserai de côté les calculs bruts mais voici quelques Haskell que vous pouvez utiliser pour vérifier cela .

Tâche

Étant donné un entier positif n comme sortie d'entrée, le nombre de boucles de Moufang qui ont l'ordre n . (l'ordre d'un groupe est la taille de l'ensemble)

Il s'agit de code-golf, donc les réponses seront notées en octets, moins d'octets seront meilleurs.

Cas de test

Voici le nombre de boucles Moufang pour les 71 premières entrées

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 octets

Merci à Mr.Xcoder pour avoir économisé quelques octets!

Utilisez la symétrie de la formule pour économiser 65 octets. Oui, c'est beaucoup.

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

Essayez-le en ligne!

Certains andpeuvent être remplacés par *, ce qui réduit le nombre d'octets mais au prix d'un temps d'exécution considérablement plus lent:

Python 3 , ??? octets

[TODO mettez le code ici]

(bien sûr, tout ne ralentit pas considérablement *le programme, seuls certains d'entre eux sont essentiels)

Non golfé:

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

Essayez-le en ligne!

_{Pas de barres de défilement ...}

Explication:

Le programme est assez simple.

• Chaque "opérateur binaire" possible est représenté par une table de Cayley (indexation 0).
• La propriété "identité" implique qu'il existe de etelle sorte que la e'e ligne et la e' e colonne soient égales [0, 1, 2, ..., n-1], ce qui est la même condition que

  le tableau Tet sa transposition ont une ligne égale à [0, 1, 2, ..., n-1].

• La propriété "annulation" équivaut à

  Chaque ligne et chaque colonne sont une permutation de [0, 1, 2, ..., n-1].

Donc, la partie

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

du code vérifie cela. (pour toutes les lignes du tableau Tet leur transposition A, le tri est égal à rangeN, et il existe une ligne dans les deux Tet Acela équivaut à lui-même d'être trié)

Les quatre conditions d'une boucle Moufang sont vérifiées manuellement.

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)

Dans le code, (a + b)est représenté par T[a][b]. (en raison de la représentation en tant que table Cayley). Utilisez la comparaison d'égalité de chaînage Python pour éviter la duplication de (z + x) + (y + z).

Cependant, parce que la formule est symétrique:

Si nous changeons les opérandes de +dans la première formule, nous obtenons la deuxième formule; et si nous changeons les opérandes de +dans la troisième formule, nous obtenons la quatrième formule avec xet la yplace échangée.

Notez que la transposition de la table Cayley est équivalente aux opérateurs binaires ayant échangé des opérandes. ( x + y -> y + x)

Enfin, tous les candidats Cayley table sont choisis parmi

permutations(permutations(rangeN), n) 

de sorte que chaque ligne est une permutation de rangeN(qui est [0, 1, 2, ..., n-1]) et il y a ndes lignes distinctes.