The Abelian Orders

Question

Some background

In math, a group is a tuple \$(G, *)\$ where \$G\$ is a set and \$*\$ is an operation on \$G\$ such that for any two elements \$x, y \in G, x * y \in G\$.

For some \$x,y,z\in G\$, basic group axioms are as follows:

• \$G\$ is closed under \$*\$, i.e. \$x * y \in G\$
• The operation \$*\$ is associative, i.e. \$x * (y * z) = (x * y) * z\$
• \$G\$ has an identity element, i.e. there exists \$e \in G\$ such that \$x * e = x\$ for all x
• The operation \$*\$ is invertible, i.e. there exist \$a, b \in G\$ such that \$a * x = y\$ and \$y * b = x\$

Okay, so those are groups. Now we define an Abelian group as a group \$(G, *)\$ such that \$*\$ is a commutative operation. That is, \$x * y = y * x\$.

Last definition. The order of a group \$(G, *)\$, denoted \$|G|\$, is the number of elements in the set \$G\$.

Task

The Abelian orders are the integers \$n\$ such that every group of order \$n\$ is Abelian. The sequence of Abelian orders is A051532 in OEIS. Your job is to produce the \$n\$th term of this sequence (1-indexed) given an integer \$n\$. You must support input up to the largest integer such that nothing will overflow.

Input can come from function arguments, command line arguments, STDIN, or whatever is convenient.

Output can be returned from a function, printed to STDOUT, or whatever is convenient. Nothing should be written to STDERR.

Score is number of bytes, shortest wins.

Examples

Here are the first 25 terms of the sequence:

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

Answer 1

CJam (35 32 bytes)

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

Online demo

Dissection

To rephrase some of the information in OEIS, the Abelian orders are the cube-free nilpotent orders; and the nilpotent orders are the numbers n for which no prime power divisor p^k | n is congruent to 1 modulo another prime divisor.

If we pass the cube-free test, the nilpotency test reduces to

• No prime factor is equal to 1 modulo another prime factor
• If the multiplicity of prime p is k, p^k must not equal 1 modulo another prime factor.

But then the second condition implies the first, so we can reduce it to

• If the multiplicity of prime p is k, p^k must not equal 1 modulo another prime factor.

Note that the word "another" is unnecessary, because p^a == 0 (mod p) for 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
}*

Answer 2

CJam, 46 45 bytes

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

Test it here.

I'm using the condition given on the OEIS page:

Let the prime factorization of \$n\$ be \$p_1^{e_1}\cdots p_r^{e_r}\$. Then \$n\$ is in this sequence if \$e_i < 3\$ for all \$i\$ and \$p_i^k \ne 1 \text{ (mod }p_j\text)\$ for all \$i, j\$ and \$1 \le k \le e_i\$ --- T. D. Noe, Mar 25 2007

I'm fairly certain this can be golfed, especially the check of the last condition.

Answer 3

Pyth, 37 bytes

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

Test suite

Uses the formula from OEIS, cubefree and no prime-power factors that are 1 mod a prime factor, other than 1.

Answer 4

Jelly, 23 bytes

ÆF*/€%þÆfn1ṭÆE<3ƊȦ
1Ç#Ṫ

Try it online!

Takes input via STDIN

How it works

This uses the same condition as the other answers, given on the OEIS page:

Let the prime factorization of \$n\$ be \$p_1^{e_1}\cdots p_r^{e_r}\$. Then \$n\$ is in this sequence if \$e_i < 3\$ for all \$i\$ and \$p_i^k \ne 1 \text{ (mod }p_j\text)\$ for all \$i, j\$ and \$1 \le k \le e_i\$

1Ç#Ṫ - Main link. Takes no arguments
1 #  - Read an integer n from STDIN. Count up k = 1, 2, 3, ... until n such k
       return true under:
 Ç   -   The helper link
   Ṫ - Return the last k

ÆF*/€%þÆfn1ṭÆE<3ƊȦ - Helper link. Takes an integer k on the left
ÆF                 - Yield the prime factorisation of k in [base, exponent] pairs
   /               - Reduce
    €              -   Each
  *                -     By exponentiation
       Æf          - Yield the list of primes whose product is k
     %þ            - Yield a modulo table of these two lists. This takes all pairs 
                     from the two lists and reduces each by modulo, yielding a
                     table of all possible modulo pairings. k can only return true
                     iff 1 is not in this table
         n1        - Map 1 -> 0 and everything else to 1
                Ɗ  - Group the previous three links into a monad f(k):
            ÆE     -   Exponents of k's prime factorisation
              <3   -   Less then 3? (vectorises)
                     This yields a binary list of all 1s if k is true else at least 1 0
           ṭ       - Tack. Append the modulo table to the binary list. Call this T
                 Ȧ - Any and all. Does T contain all 1s when flattened and T is non-empty?