|
%I #26 Oct 24 2022 10:59:25
%S 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,
%T 9,16,2801,7,1093,17,1,4,307,5,25,36,19531,32,73,1,3,27,5,30941,9,29,
%U 32,757,11,1,3,7,16,88741,63,43,64,19,44,23
%N 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.
%C Maximal order of degree-n irreducible polynomials over GF(prime(k)) is prime(k)^n-1 and thus A(n,k) < prime(k)^n.
%H Alois P. Heinz, <a href="/A213224/b213224.txt">Antidiagonals n = 1..45, flattened</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PolynomialOrder.html">Polynomial Order</a>
%F 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) = {}.
%e 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).
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 3, 4, 3, 4, 3, 7, 3, 4, ...
%e 7, 13, 31, 9, 7, 9, 307, 27, ...
%e 5, 5, 13, 5, 16, 5, 5, 16, ...
%e 31, 11, 11, 2801, 25, 30941, 88741, 151, ...
%e 9, 7, 7, 36, 9, 63, 7, 7, ...
%e 127, 1093, 19531, 29, 43, 5229043, 25646167, 701, ...
%e 17, 32, 32, 64, 32, 32, 128, 17, ...
%p with(numtheory):
%p M:= proc(n, i) option remember;
%p divisors(ithprime(i)^n-1) minus U(n-1, i)
%p end:
%p U:= proc(n, i) option remember;
%p `if`(n=0, {}, M(n, i) union U(n-1, i))
%p end:
%p A:= (n, k)-> min(M(n, k)[]):
%p seq(seq(A(n, d+1-n), n=1..d), d=1..14);
%t 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 *)
%Y Columns k=1-10 give: A212953, A218356, A218357, A218358, A218359, A218360, A218361, A218362, A218363, A218364.
%Y Columns k=1-10 are first columns of: A059912, A212906, A212485, A212486, A218336, A218337, A218338, A218339, A218340, A218341.
%Y Cf. A212737 (all orders).
%K nonn,tabl
%O 1,3
%A _Alois P. Heinz_, Jun 06 2012
|
