OFFSET
1,3
COMMENTS
Maximal order of degree-n irreducible polynomials over GF(prime(k)) is prime(k)^n-1 and thus A(n,k) < prime(k)^n.
LINKS
Alois P. Heinz, Antidiagonals n = 1..45, flattened
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Polynomial Order
FORMULA
A(n,k) = min(M(n,k)) with M(n,k) = {d : d|(prime(k)^n-1)} \ U(n-1,k) and U(n,k) = M(n,k) union U(n-1,k) for n>0, U(0,k) = {}.
EXAMPLE
A(4,1) = 5: The degree-4 irreducible polynomials p over GF(prime(1)) = GF(2) are 1+x+x^2+x^3+x^4, 1+x+x^4, 1+x^3+x^4. Their orders (i.e., the smallest integer e for which p divides x^e+1) are 5, 15, 15, and the minimal order is 5. (1+x+x^2+x^3+x^4) * (1+x) == x^5+1 (mod 2).
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
3, 4, 3, 4, 3, 7, 3, 4, ...
7, 13, 31, 9, 7, 9, 307, 27, ...
5, 5, 13, 5, 16, 5, 5, 16, ...
31, 11, 11, 2801, 25, 30941, 88741, 151, ...
9, 7, 7, 36, 9, 63, 7, 7, ...
127, 1093, 19531, 29, 43, 5229043, 25646167, 701, ...
17, 32, 32, 64, 32, 32, 128, 17, ...
MAPLE
with(numtheory):
M:= proc(n, i) option remember;
divisors(ithprime(i)^n-1) minus U(n-1, i)
end:
U:= proc(n, i) option remember;
`if`(n=0, {}, M(n, i) union U(n-1, i))
end:
A:= (n, k)-> min(M(n, k)[]):
seq(seq(A(n, d+1-n), n=1..d), d=1..14);
MATHEMATICA
M[n_, i_] := M[n, i] = Divisors[Prime[i]^n - 1] ~Complement~ U[n-1, i]; U[n_, i_] := U[n, i] = If[n == 0, {}, M[n, i] ~Union~ U[n-1, i]]; A[n_, k_] := Min[M[n, k]]; Table[Table[A[n, d+1-n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jun 06 2012
STATUS
approved