This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A057646 a(n) = number of trinomials x^n + x^k + 1 that are irreducible over GF(2) for some k with n > k > 0. 4

%I

%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) = 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.

%t Do[ c = 0; Do[ If[ ToString[ Factor[ 1 + x^k + x^n, Modulus -> 2 ] ] == ToString[ 1 + x^k + x^n ], c++ ], {k, 1, n - 1} ]; Print[ c ], {n, 2, 100} ]

%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.

%K nonn,easy,nice

%O 2,2

%A _Robert G. Wilson v_, Oct 11 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 20 15:43 EDT 2019. Contains 321345 sequences. (Running on oeis4.)