Некоторый фон

В математике, A группа представляет собой набор ( G , •) , где G представляет собой набор и • представляет собой операцию на G такое , что для любых двух элементов х и у в G , х • у также находится в G .

Для некоторых x , y , z в G основные аксиомы группы следующие:

• G будет закрыта в •, т.е. х • у в G
• Операция • является ассоциативной , то есть x • ( y • z ) = ( x • y ) • z
• G имеет единичный элемент, т. Е. В G существует такое e , что x • e = x для всех x
• Операция • является обратимой , т.е. существует , Ь в G таким образом, чтобы • х = у и у • Ь = х

Итак, это группы. Теперь мы определили абелеву группу как группу ( G , •) такую, что • является коммутативной операцией. То есть x • y = y • x .

Последнее определение Порядок группы ( G , •), обозначаемое | G |, является число элементов в множестве G .

задача

Абелевы порядки - это такие целые числа n , что каждая группа порядка n абелева. Последовательность абелевых порядков в OEIS A051532 . Ваша задача - создать n- й член этой последовательности (1-индексированный) с целым числом n . Вы должны поддерживать ввод вплоть до наибольшего целого числа, чтобы ничего не было переполнено.

Входные данные могут поступать из аргументов функции, аргументов командной строки, STDIN или чего угодно.

Вывод может быть возвращен из функции, распечатан в STDOUT или любым другим удобным способом. Ничто не должно быть написано в STDERR.

Счет - это количество байтов, кратчайшие выигрыши.

Примеры

Вот первые 25 членов последовательности:

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

CJam ( 35 32 байта)

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

Онлайн демо

рассечение

Чтобы перефразировать некоторую информацию в OEIS, абелевы порядки являются нильпотентными порядками без кубов ; и нильпотентные порядки - это числа, nдля которых ни один простой делитель мощности не p^k | nявляется конгруэнтным по 1модулю другого простого делителя.

Если мы пройдем тест без кубов, тест нильпотентности сводится к

• Нет простого множителя равно 1модулю другого простого множителя
• Если кратность простого числа pравна k, p^kне должно быть равным 1по модулю другого простого множителя.

Но тогда второе условие подразумевает первое, поэтому мы можем уменьшить его до

• Если кратность простого числа pравна k, p^kне должно быть равным 1по модулю другого простого множителя.

Обратите внимание, что слово «другое» не нужно, потому что p^a == 0 (mod p)для 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
}*

CJam, 46 45 байт

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

Проверьте это здесь.

Я использую условие, указанное на странице OEIS:

Пусть первичная факторизация nбудет . Тогда есть в этой последовательности, если для всех и не равно для всех а и . --- TD Noe , 25 марта 2007p1e1...prernei < 3ipik1 (mod pj)ij1 ≤ k ≤ ei

Я вполне уверен, что это может быть в гольфе, особенно проверка последнего условия.

Pyth, 37 байт

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

Тестирование

Использует формулу из OEIS, без кубов и без простых коэффициентов мощности, которые являются 1 mod простым фактором, кроме 1.