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 and y in G, x • y is also 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 invertable, i.e. there exist a, b in G such that a • x = y and y • b = x

Okay, so those are groups. Now we defined 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 nth 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 p1e1...prer. Then n is in this sequence if ei < 3 for all i and pik does not equal 1 (mod pj) for all i and j and 1 ≤ k ≤ ei. --- 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.