|
%I #26 May 11 2021 01:52:05
%S 1,2,2,2,3,4,0,4,2,2,4,0,2,6,0,6,5,0,4,4,2,4,0,4,0,0,8,2,4,8,0,4,2,2,
%T 6,0,0,6,0,4,2,0,2,0,2,8,0,8,0,0,8,0,5,4,0,8,2,0,12,0,2,10,0,4,2,0,4,
%U 0,0,10,0,6,2,0,2,0,0,4,0,6,0,0,14,0,2,2,0,2,2,0,2,2,2,4,0,8,4,0,10
%N a(n) is the number of trinomials x^n + x^k + 1 that are irreducible over GF(2) for some k with n > k > 0.
%C Brent, Hart, Kruppa, and Zimmermann found that a(57885161) = 0. - _Charles R Greathouse IV_, May 30 2013
%H T. D. Noe, <a href="/A057646/b057646.txt">Table of n, a(n) for n = 2..500</a>
%H Paul Zimmermann, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;ebe12819.1305">There is no primitive trinomial of degree 57885161 over GF(2)</a>, posting to NMBRTHRY mailing list [<a href="http://webloria.loria.fr/~zimmerma/irred/57885161.txt">alternate link</a>]
%e a(7) = 4 because 1 + x + x^7 = 1 + x + x^7, 1 + x^2 + x^7 = (1 + x + x^2)*(1 + x + x^2 + x^4 + x^5), 1 + x^3 + x^7 = 1 + x^3 + x^7, 1 + x^4 + x^7 = 1 + x^4 + x^7, 1 + x^5 + x^7 = (1 + x + x^2)*(1 + x + x^3 + x^4 + x^5) and 1 + x^6 + x^7 = 1 + x^6 + x^7. Thus there are 4 trinomial expressions which cannot be factored over GF(2) and 2 trinomial expressions which do factor.
%o (PARI) a(n)=sum(s=1,n-1,polisirreducible((x^n+x^s+1)*Mod(1,2))) \\ _Charles R Greathouse IV_, May 30 2013
%Y For n such that a(n) > 0 see A073571.
%Y Cf. A014580 (irreducible polynomials over GF(2) encoded as binary numbers), A344146.
%K nonn,easy,nice
%O 2,2
%A _Robert G. Wilson v_, Oct 11 2000
|
