cp's OEIS Frontend

A212953 Minimal order of degree-n irreducible polynomials over GF(2).

%I A212953 #38 Feb 16 2025 08:33:17
%S A212953 1,3,7,5,31,9,127,17,73,11,23,13,8191,43,151,257,131071,19,524287,25,
%T A212953 49,69,47,119,601,2731,262657,29,233,77,2147483647,65537,161,43691,71,
%U A212953 37,223,174763,79,187,13367,147,431,115,631,141,2351,97,4432676798593,251
%N A212953 Minimal order of degree-n irreducible polynomials over GF(2).
%C A212953 a(n) = smallest odd m such that A002326((m-1)/2) = n. - _Thomas Ordowski_, Feb 04 2014
%C A212953 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 A212953 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 A212953 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 A212953 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>
%H A212953 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PolynomialOrder.html">Polynomial Order</a>
%F A212953 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 A212953 a(n) = A059912(n,1) = A213224(n,1).
%e A212953 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 A212953 with(numtheory):
%p A212953 M:= proc(n) option remember;
%p A212953       divisors(2^n-1) minus U(n-1)
%p A212953     end:
%p A212953 U:= proc(n) option remember;
%p A212953       `if`(n=0, {}, M(n) union U(n-1))
%p A212953     end:
%p A212953 a:= n-> min(M(n)[]):
%p A212953 seq(a(n), n=1..50);
%t A212953 M[n_] := M[n] = Divisors[2^n-1] ~Complement~ U[n-1];
%t A212953 U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n-1]];
%t A212953 a[n_] := Min[M[n]];
%t A212953 Array[a, 50] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)
%Y A212953 Cf. A003060, A059912, A213224.
%K A212953 nonn
%O A212953 1,2
%A A212953 _Alois P. Heinz_, Jun 01 2012