# The Abelian Orders

## 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\$$.

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


## 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
}*

• Thank you for the very thorough and intriguing explanation! :) – Fax Machine Dec 31 '15 at 5:06

## 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.

# 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.

# 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:
Ṫ - 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
`