login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A193498 n such that certain polynomials are irreducible over GF(2), see first comment. 0
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 16, 18, 21, 24, 32, 34, 48, 64, 65, 74, 81, 96, 117, 121, 128, 144, 153, 161, 192, 241, 256, 258, 288, 321, 384, 493, 512, 611, 617, 768, 974, 1024 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Recursively build matrices by setting M(0) = [1], and M(k+1)=[M(k),E(k); E(k),Z(k)] where E(k) is the N x N unit matrix and Z(k) is the N x N zero matrix (and N=2^k). Let c(x) the characteristic polynomial (over GF(2)) of the upper left n x n submatrix. If c(x), divided by the least power of x with nonzero coefficient, is irreducible over GF(2) then n is a term of this sequence (see example).

All powers of 2 are terms, corresponding to self-reciprocal polynomials, see Theorem 7 of the Cohen reference.

REFERENCES

Stephen D. Cohen, "The explicit construction of irreducible polynomials over finite fields", Designs, Codes and Cryptography, vol.2, no.2, pp. 169-174, (June 1992).

LINKS

Table of n, a(n) for n=1..43.

Joerg Arndt, Matters Computational (The Fxtbook), figure 40.9-G on p.854

EXAMPLE

The 16 x 16 matrix M(4) is (dots for zeros):

111.1...1.......

1..1.1...1......

1.....1...1.....

.1.....1...1....

1...........1...

.1...........1..

..1...........1.

...1...........1

1...............

.1..............

..1.............

...1............

....1...........

.....1..........

......1.........

.......1........

The characteristic polynomial of the 9 x 9 (upper left) submatrix is c(x)=x^9 + x^8 + x^5 + x^3 + x^2, and C(x)/x^2 = x^7 + x^6 + x^3 + x + 1 is irreducible over GF(2), so 9 is a term.

PROG

(PARI)

Mrec(t)=

{ /* Auxiliary routine to build up matrices */

    local(n, M);

    n = matsize(t)[1];

    M = matrix(2*n, 2*n); /* double the size */

    /* lower left and upper right: unit matrices */

    for (k=1, n, M[k, n+k]=1; M[n+k, k]=1; );

    /* upper left: copy of smaller matrix */

    for (k=1, n, for (j=1, n, M[k, j]=t[k, j]; ); );

    return ( M );

}

Mfunc(n)=

{ /* Compute matrix of size 2^n */

    local(M);

    M = matrix(1, 1, r, c, 1 );  /* start with unit matrix */

    for (k=1, n, M=Mrec(M) );  /* build up to size 2^n */

    return( M * Mod(1, 2) );  /* over GF(2) */

}

{ for (k=1, N,

  K =matrix(k, k, r, c, M[r, c]);

  C = charpoly(K, , 2);  /* Hessenberg is much faster than Berkowitz */

  c = polrecip(C);  c = polrecip(c); /* get rid of trivial factor (power of x) */

  if ( polisirreducible(c), print1(k, ", ") );

); }

CROSSREFS

Sequence in context: A007602 A167620 A169935 * A239087 A095227 A131366

Adjacent sequences:  A193495 A193496 A193497 * A193499 A193500 A193501

KEYWORD

nonn

AUTHOR

Joerg Arndt, Aug 17 2011

STATUS

approved

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 14 22:42 EST 2019. Contains 329987 sequences. (Running on oeis4.)