login
A213224
Minimal order A(n,k) of degree-n irreducible polynomials over GF(prime(k)); square array A(n,k), n>=1, k>=1, read by antidiagonals.
11
1, 1, 3, 1, 4, 7, 1, 3, 13, 5, 1, 4, 31, 5, 31, 1, 3, 9, 13, 11, 9, 1, 7, 7, 5, 11, 7, 127, 1, 3, 9, 16, 2801, 7, 1093, 17, 1, 4, 307, 5, 25, 36, 19531, 32, 73, 1, 3, 27, 5, 30941, 9, 29, 32, 757, 11, 1, 3, 7, 16, 88741, 63, 43, 64, 19, 44, 23
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
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
Columns k=1-10 are first columns of: A059912, A212906, A212485, A212486, A218336, A218337, A218338, A218339, A218340, A218341.
Cf. A212737 (all orders).
Sequence in context: A357182 A028861 A081521 * A210218 A086273 A054143
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jun 06 2012
STATUS
approved