Les ordres abéliens

17

Quelques antécédents

En mathématiques, un groupe est un tuple ( G , •) où G est un ensemble et • est une opération sur G telle que pour deux éléments quelconques x et y dans G , xy est également dans G .

Pour certains x , y , z dans G , les axiomes de groupe de base sont les suivants:

  • G est fermé sous •, c'est-à-dire xy dans G
  • L'opération • est associative , c'est-à-dire x • ( yz ) = ( xy ) • z
  • G a un élément d' identité , c'est-à-dire qu'il existe e dans G tel que xe = x pour tout x
  • L'opération • est inversible , c'est-à-dire qu'il existe a , b dans G tels que ax = y et yb = x

D'accord, ce sont donc des groupes. Maintenant, nous avons défini un groupe abélien comme un groupe ( G , •) tel que • est une opération commutative . Autrement dit, x y = y x .

Dernière définition. L' ordre d'un groupe ( G , •), noté | G |, est le nombre d'éléments dans l'ensemble G .

Tâche

Les ordres abéliens sont les entiers n tels que chaque groupe d'ordre n est abélien. La séquence des ordres abéliens est A051532 dans OEIS. Votre travail consiste à produire n ème terme de cette séquence (indexé 1) étant donné un entier n . Vous devez prendre en charge l'entrée jusqu'au plus grand entier de sorte que rien ne déborde.

L'entrée peut provenir d'arguments de fonction, d'arguments de ligne de commande, de STDIN ou de tout ce qui est pratique.

La sortie peut être retournée à partir d'une fonction, imprimée sur STDOUT ou tout ce qui est pratique. Rien ne doit être écrit à STDERR.

Le score est le nombre d'octets, les gains les plus courts.

Exemples

Voici les 25 premiers termes de la séquence:

1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 29, 31, 33, 35, 37, 41, 43, 45, 47, 49, 51
Télécopieur
la source
1
En relation.
Martin Ender

Réponses:

6

CJam ( 35 32 octets)

0q~{{)_mF_z~2f>@::#@m*::%+1&}g}*

Démo en ligne

Dissection

Pour reformuler certaines informations dans OEIS, les ordres abéliens sont les ordres nilpotents sans cube ; et les ordres nilpotents sont les nombres npour lesquels aucun diviseur de puissance principalep^k | n correspond à1 modulo un autre diviseur premier.

Si nous réussissons le test sans cube, le test de nilpotency se réduit à

  • Aucun facteur premier n'est égal à 1 modulo un autre facteur premier
  • Si la multiplicité de prime pest k, p^kne doit pas être égal à 1modulo un autre facteur premier.

Mais alors la deuxième condition implique la première, donc nous pouvons la réduire à

  • Si la multiplicité de prime pest k, p^kne doit pas être égal à 1modulo un autre facteur premier.

Notez que le mot "autre" est inutile, car p^a == 0 (mod p)pour a > 0.

0q~{       e# Loop n times starting from a value less than the first Abelian order
  {        e#   Find a number which doesn't satisfy the condition
    )_     e#     Increment and duplicate to test the condition on the copy
    mF     e#     Find prime factors with multiplicity
    _z~    e#     Duplicate and split into the primes and the multiplicities
    2f>    e#     Map the multiplicities to whether or not they're too high
    @::#   e#     Bring factors with multiplicities to top and expand to array of
           e#     maximal prime powers
    @m*::% e#     Cartesian product with the primes and map modulo, so for each
           e#     prime power p^k and prime q we have p^k % q.
    +      e#     Combine the "multiplicity too high" and the (p^k % q) values
    1&     e#     Check whether either contains a 1
  }g
}*
Peter Taylor
la source
1
Merci pour l'explication très complète et intrigante! :)
Télécopieur
5

CJam, 46 45 octets

0{{)_mf_e`_:e>3a>\{~\,:)f#}%@fff%e_1e=|}g}ri*

Testez-le ici.

J'utilise la condition donnée sur la page OEIS:

Soit la factorisation première de nbe . Ensuite , est dans cette séquence si pour tous et ne est pas égal pour tous et et . --- TD Noe , 25 mars 2007p1e1...prernei < 3ipik1 (mod pj)ij1 ≤ k ≤ ei

Je suis assez certain que cela peut être joué au golf, en particulier la vérification de la dernière condition.

Martin Ender
la source
3

Pyth, 37 octets

e.f!&tZ|f>hT2JrPZ8}1%M*eMJs.b*LYSNJ)Q

Suite de tests

Utilise la formule d'OEIS, sans cube et sans facteur de puissance première qui est un facteur premier de 1 mod, autre que 1.

isaacg
la source