Zakony Abelowe

17

Trochę tła

W matematyce grupa jest krotką ( G , •), gdzie G jest zbiorem, a • jest operacją na G, tak że dla dowolnych dwóch elementów x i y w G , xy jest również w G .

Dla niektórych x , y , z w G podstawowe aksjomaty grupy są następujące:

  • G jest zamknięte pod •, tzn. Xy w G
  • Operacja • jest asocjacyjna , tzn. X • ( yz ) = ( xy ) • z
  • G ma identyfikacyjny element, czyli istnieje e na G w taki sposób, xe = x dla wszystkich x
  • Operacja • jest invertable , to istnieje , b na G w taki sposób, • x = r i rb = x

Okej, więc to są grupy. Teraz zdefiniowaliśmy grupę abelową jako grupę ( G , •) taką, że • jest operacją przemienną . To znaczy, xy = y x .

Ostatnia definicja. Kolejność grupy ( G , •), oznaczoną | G |, to liczba elementów w zestawie G .

Zadanie

Porządki abelowe są liczbami całkowitymi n takimi, że każda grupa rzędu n jest abelowa. Sekwencja zleceń abelowych to A051532 w OEIS. Twoim zadaniem jest wygenerowanie n- tego wyrażenia z tej sekwencji (indeksowane 1), biorąc pod uwagę liczbę całkowitą n . Musisz obsługiwać dane wejściowe do największej liczby całkowitej, aby nic się nie przepełniło.

Dane wejściowe mogą pochodzić z argumentów funkcji, argumentów wiersza poleceń, STDIN lub dowolnego innego wygodnego elementu.

Dane wyjściowe można zwrócić z funkcji, wydrukować do STDOUT lub cokolwiek jest wygodne. Nic nie należy pisać do STDERR.

Wynik to liczba bajtów, najkrótsze wygrane.

Przykłady

Oto 25 pierwszych terminów sekwencji:

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
Faks
źródło
1
Związane z.
Martin Ender,

Odpowiedzi:

6

CJam ( 35 32 bajty)

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

Demo online

Sekcja

Aby przeformułować niektóre informacje w OEIS, zamówienia abelowe są pozbawionymi kostek zerowymi zamówieniami ; a zerowe porządki są liczbami, ndla których żaden dzielnik mocy pierwotnej nie p^k | njest zgodny1 modulo innego głównego dzielnika.

Jeśli zdamy test bez kostki, test nilpotencji zmniejsza się do

  • Żaden czynnik pierwszy nie jest równy 1modulo innemu czynnikowi pierwszemu
  • Jeśli wielość Prime pjest k, p^knie musi równe 1modulo kolejną doskonałą czynnik.

Ale wtedy drugi warunek implikuje pierwszy, więc możemy go zredukować do

  • Jeśli wielość Prime pjest k, p^knie musi równe 1modulo kolejną doskonałą czynnik.

Zauważ, że słowo „inny” nie jest konieczne, ponieważ p^a == 0 (mod p)dla 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
źródło
1
Dziękujemy za bardzo dokładne i intrygujące wyjaśnienie! :)
Faks
5

CJam, 46 45 bajtów

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

Sprawdź to tutaj.

Korzystam z warunku podanego na stronie OEIS:

Niech głównym czynnikiem nbędzie . Wtedy to w tej kolejności, jeśli dla wszystkich a nie równe dla wszystkich i i . --- TD Noe , 25 marca 2007 rp1e1...prernei < 3ipik1 (mod pj)ij1 ≤ k ≤ ei

Jestem całkiem pewien, że można to zagrać w golfa, zwłaszcza sprawdzenie ostatniego warunku.

Martin Ender
źródło
3

Pyth, 37 bajtów

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

Zestaw testowy

Korzysta z formuły z OEIS, wolnej od sześciennej i żadnych współczynników mocy pierwotnej, które wynoszą 1 mod współczynnik pierwotny, inny niż 1.

isaacg
źródło