cp's OEIS Frontend

A002475 Numbers k such that x^k + x + 1 is irreducible over GF(2).

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