|
%I M0544 N0194 #89 Dec 23 2023 18:58:58
%S 0,2,3,4,6,7,9,15,22,28,30,46,60,63,127,153,172,303,471,532,865,900,
%T 1366,2380,3310,4495,6321,7447,10198,11425,21846,24369,27286,28713,
%U 32767,34353,46383,53484,62481,83406,87382,103468,198958,248833
%N Numbers k such that x^k + x + 1 is irreducible over GF(2).
%C k=1 is excluded since the polynomial "1" is not normally regarded as irreducible.
%C 2^(A073639(m)) - 1 is a term for all m. - _Joerg Arndt_, Aug 23 2015
%C Any subsequent terms are > 300000. - _Lucas A. Brown_, Nov 28 2022
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 975.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
%H Lucas A. Brown, <a href="https://github.com/lucasaugustus/oeis/blob/main/irred_trinom_f2.py">Python program</a>.
%H Lucas A. Brown, <a href="https://github.com/lucasaugustus/oeis/blob/main/irred_trinom_f2.sage">Sage program</a>.
%H N. Zierler, <a href="http://dx.doi.org/10.1016/S0019-9958(70)90264-0">On x^n+x+1 over GF(2)</a>, Information and Control, 16 1970 502-505.
%H <a href="/index/Tri#trinomial">Index entries for sequences related to trinomials over GF(2)</a>
%p select(n -> Irreduc(x^n+x+1) mod 2, [0,$2..10000]); # _Robert Israel_, Aug 09 2015
%t Do[ If[ ToString[ Factor[ x^n + x + 1, Modulus -> 2 ] ] == ToString[ x^n + x + 1 ], Print [ n ] ], {n, 0, 28713} ]
%t Select[Range[1000], IrreduciblePolynomialQ[x^# + x + 1, Modulus -> 2] &] (* _Robert Price_, Sep 19 2018 *)
%o (Magma) P<x> := PolynomialRing(GaloisField(2)); for n := 2 to 100000 do if IsIrreducible(x^n+x+1) then print(n); end if; endfor;
%o (Sage)
%o P.<x> = GF(2)[]
%o for n in range(90):
%o if (x^n+x+1).is_irreducible():
%o print(n) # _Ruperto Corso_, Dec 11 2011
%o (PARI)
%o for (n=1,10^6, if ( polisirreducible(Mod(1,2)*(x^n+x+1)), print1(n,", ") ) );
%o /* _Joerg Arndt_, Apr 28 2012 */
%o (PARI) is(n)=if(n>3&&[1,0,1,1,0,1,0,0][n%8+1], return(0)); polisirreducible(Mod('x^n+'x+1,2)) \\ _Charles R Greathouse IV_, Jun 04 2015
%Y Cf. A001153, A073639, A057496, A223938 (n such that x^n-x-1 is irreducible over GF(3)).
%K nonn,hard,more,nice
%O 1,2
%A _N. J. A. Sloane_
%E Two more terms from _Paul Zimmermann_, Sep 05 2002
%E a(37)-a(39) from _Max Alekseyev_, Oct 29 2011
%E a(40)-a(41) from _Ruperto Corso_, Dec 11 2011
%E a(42) from _Manfred Scheucher_, Jun 04 2015
%E a(43) from _Manfred Scheucher_, Aug 09 2015
%E a(44) from _Lucas A. Brown_, Nov 28 2022
|
