|
%I #37 Apr 30 2022 15:19:08
%S 1,3,7,5,31,9,127,17,73,11,23,13,8191,43,151,257,131071,19,524287,25,
%T 49,69,47,119,601,2731,262657,29,233,77,2147483647,65537,161,43691,71,
%U 37,223,174763,79,187,13367,147,431,115,631,141,2351,97,4432676798593,251
%N Minimal order of degree-n irreducible polynomials over GF(2).
%C a(n) = smallest odd m such that A002326((m-1)/2) = n. - _Thomas Ordowski_, Feb 04 2014
%C For n > 1; n < a(n) < 2^n, wherein a(n) = n+1 iff n+1 is A001122 a prime with primitive root 2, or a(n) = 2^n-1 iff n is a Mersenne exponent A000043. - _Thomas Ordowski_, Feb 08 2014
%D W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer 2004, Third Edition, 4.3 Factorization of Prime Ideals in Extensions. More About the Class Group (Theorem 4.33), 4.4 Notes to Chapter 4 (Theorem 4.40). - Regarding the first comment.
%H Max Alekseyev, <a href="/A212953/b212953.txt">Table of n, a(n) for n = 1..1236</a> (first 179 terms from Alois P. Heinz)
%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) = min(M(n)) with M(n) = {d : d|(2^n-1)} \ U(n-1) and U(n) = M(n) union U(n-1) for n>0, U(0) = {}.
%F a(n) = A059912(n,1) = A213224(n,1).
%e For n=4 the degree-4 irreducible polynomials p over 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. (Example: (1+x+x^2+x^3+x^4) * (1+x) == x^5+1 (mod 2)). Thus the minimal order is 5 and a(4) = 5.
%p with(numtheory):
%p M:= proc(n) option remember;
%p divisors(2^n-1) minus U(n-1)
%p end:
%p U:= proc(n) option remember;
%p `if`(n=0, {}, M(n) union U(n-1))
%p end:
%p a:= n-> min(M(n)[]):
%p seq(a(n), n=1..50);
%t M[n_] := M[n] = Divisors[2^n-1] ~Complement~ U[n-1];
%t U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n-1]];
%t a[n_] := Min[M[n]];
%t Array[a, 50] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)
%Y Cf. A003060, A059912, A213224.
%K nonn
%O 1,2
%A _Alois P. Heinz_, Jun 01 2012
|
