Las órdenes abelianas

17

Algunos antecedentes

En matemáticas, un grupo es una tupla ( G , •) donde G es un conjunto y • es una operación en G tal que para cualquier par de elementos de x y y en G , xy también está en G .

Para algunos x , y , z en G , los axiomas de grupo básicos son los siguientes:

  • G está cerrado debajo de •, es decir, xy en G
  • La operación • es asociativa , es decir, x • ( yz ) = ( xy ) • z
  • G tiene un elemento de identidad , es decir, existe e en G tal que xe = x para todo x
  • La operación • es invertable , es decir, existen a , b en G de modo que ax = y e yb = x

Bien, entonces esos son grupos. Ahora definimos un grupo abeliano como un grupo ( G , •) tal que • es una operación conmutativa . Es decir, xy = yx .

Última definición El orden de un grupo ( G , •), denotado | G |, es el número de elementos en el conjunto G .

Tarea

Las órdenes abelianas son los enteros n, de modo que cada grupo de orden n es abeliano. La secuencia de órdenes abelianas es A051532 en OEIS. Su trabajo es producir el n º término de esta secuencia (1-indexada) dado un número entero n . Debe admitir la entrada hasta el entero más grande de modo que nada se desborde.

La entrada puede provenir de argumentos de función, argumentos de línea de comando, STDIN o lo que sea conveniente.

La salida puede devolverse desde una función, imprimirse en STDOUT o lo que sea conveniente. No se debe escribir nada en STDERR.

La puntuación es el número de bytes, las victorias más cortas.

Ejemplos

Aquí están los primeros 25 términos de la secuencia:

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
Máquina de fax
fuente
1
Relacionado.
Martin Ender

Respuestas:

6

CJam ( 35 32 bytes)

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

Demostración en línea

Disección

Para reformular parte de la información en OEIS, las órdenes abelianas son las órdenes nilpotentes sin cubos ; y las órdenes nilpotentes son los números npara los cuales ningún divisor de potencia primo p^k | nes congruente con el 1módulo de otro divisor primo.

Si pasamos la prueba sin cubo, la prueba de nilpotencia se reduce a

  • Ningún factor primo es igual al 1módulo de otro factor primo
  • Si la multiplicidad de primos pes k, p^kno debe ser igual 1módulo otro factor primo.

Pero entonces la segunda condición implica la primera, por lo que podemos reducirla a

  • Si la multiplicidad de primos pes k, p^kno debe ser igual 1módulo otro factor primo.

Tenga en cuenta que la palabra "otro" es innecesaria, porque p^a == 0 (mod p)para 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
fuente
1
¡Gracias por la explicación muy completa e intrigante! :)
Fax Machine
5

CJam, 46 45 bytes

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

Pruébalo aquí.

Estoy usando la condición dada en la página OEIS:

Deja que la factorización prima de nbe . Entonces está en esta secuencia si para todos y no es igual para todos y y . --- TD Noe , 25 de marzo de 2007p1e1...prernei < 3ipik1 (mod pj)ij1 ≤ k ≤ ei

Estoy bastante seguro de que esto se puede jugar, especialmente el control de la última condición.

Martin Ender
fuente
3

Pyth, 37 bytes

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

Banco de pruebas

Utiliza la fórmula de OEIS, sin cubo y sin factores de potencia primos que son 1 mod un factor primo, que no sea 1.

isaacg
fuente