login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Columns k=1-10 give: A212953, A218356, A218357, A218358, A218359, A218360, A218361, A218362, A218363, A218364.

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: A049918 A028861 A081521 * A210218 A086273 A054143

Adjacent sequences:  A213221 A213222 A213223 * A213225 A213226 A213227

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jun 06 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 13:41 EST 2020. Contains 331149 sequences. (Running on oeis4.)