cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A344143 Indices k such that A344141(k) and A344142(k) are not equal.

Original entry on oeis.org

33, 34, 36, 37, 42, 49, 54, 55, 58, 59, 62, 65, 68, 71, 72, 73, 74, 76, 78, 79, 80, 82, 86, 87, 88, 89, 90, 91, 92, 94, 95, 96, 98, 100, 102, 103, 106, 107, 108, 110, 111, 113, 115, 118, 121, 124, 125, 126, 131, 132, 133, 134, 135, 137, 138, 139, 140, 141
Offset: 1

Views

Author

Jianing Song, May 10 2021

Keywords

Comments

A344141 and A344142 are two different methods of finding the "first irreducible GF(2)[X] polynomial of degree k". Sequence gives k such that this two methods disagree.
Obviously, k is a term if and only if A000120(A344141(k)) != A000120(A344142(k)).

Examples

			33 is a term, since lexicographically the first irreducible GF(2)[X] polynomial of degree 33 is x^33 + x^6 + x^3 + x + 1, while lexicographically the first irreducible GF(2)[X] polynomial with the lowest possible number of terms is x^33 + x^10 + 1.
37 is a term, since lexicographically the first irreducible GF(2)[X] polynomial of degree 37 is x^37 + x^5 + x^4 + x^3 + x^2 + x + 1, while lexicographically the first irreducible GF(2)[X] polynomial with the lowest possible number of terms is x^37 + x^6 + x^4 + x + 1.
54 is a term, since lexicographically the first irreducible GF(2)[X] polynomial of degree 54 is x^54 + x^6 + x^5 + x^4 + x^3 + x^2 + 1, while lexicographically the first irreducible GF(2)[X] polynomial with the lowest possible number of terms is x^54 + x^9 + 1.

Links

Crossrefs

Cf. A014580, A344141, A344142, A000120.

Programs

  • PARI
    isA344143(n) = my(k=A344142(n)-1); while(k>=2^n, if(polisirreducible(Mod(Pol(binary(k)), 2)), return(1), k--)); 0 \\ See A344142 for its program, assuming that an irreducible polynomial of degree n with at most 5 terms exists for every n.

A344186 a(n) = A344142(n) - 2^n.

Original entry on oeis.org

0, 3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43, 9, 9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141, 1025, 129, 5, 513, 83, 99, 17, 57, 9, 129, 89, 33, 27, 3, 33, 45, 513, 29, 75, 9, 71, 513, 129, 149, 17, 524289, 149, 3, 39, 536870913, 3, 27, 262145, 9, 39, 513, 101, 43
Offset: 1

Views

Author

Jianing Song, May 11 2021

Keywords

Comments

A more intuitive version of A344142.
In A057496 it is stated that if x^n + x^3 + x^2 + x + 1 is irreducible, then so is x^n + x^3 + 1. It follows that no term can be equal to 15.
It is conjectured that an irreducible polynomial of degree n with 5 terms exists for every n. It follows from the conjecture that for n >= 2, a(n) is of the form 2^k + 1 or an odd number with Hamming weight 4.
It is conjectured that no term can be of the form P_m(2^k), where P_m(x) = Product_{i>=0} (1 + x^(2^(d_i)))^(c_i) if the binary representation of m is m = Sum_{i>=0} c_i * 2^(d_i), k is an odd number. See my conjecture in A344177.

Examples

			See A344142.

Links

Crossrefs

Cf. A014580, A344142, A344185, A344177.

Programs

  • PARI
    A344186(n) = if(n==1, 0, for(k=1, n-1, if(polisirreducible(Mod(x^n+x^k+1, 2)), return(2^k+1))); for(a=3, n-1, for(b=2, a-1, for(c=1, b-1, if(polisirreducible(Mod(x^n+x^a+x^b+x^c+1, 2)), return(2^a+2^b+2^c+1)))))) \\ Assuming that an irreducible polynomial of degree n with at most 5 terms exists for every n.

A344141 Lexicographically first irreducible polynomial over GF(2) of degree n, evaluated at X = 2.

Original entry on oeis.org

2, 7, 11, 19, 37, 67, 131, 283, 515, 1033, 2053, 4105, 8219, 16417, 32771, 65579, 131081, 262153, 524327, 1048585, 2097157, 4194307, 8388641, 16777243, 33554441, 67108891, 134217767, 268435459, 536870917, 1073741827, 2147483657, 4294967437, 8589934667
Offset: 1

Views

Author

Jianing Song, May 10 2021

Keywords

Comments

a(n) is the smallest term in A014580 that is greater than or equal to 2^n.
To get a(n), you first ask the question: "Is x^n irreducible over GF(2)?" If it is not, you then ask "is x^n + 1 irreducible over GF(2)", then "is x^n + x irreducible over GF(2)", then "is x^n + x + 1 irreducible over GF(2)", until you get an irreducible polynomial, then evaluate it at x = 2.
Note that in general you do not get an irreducible polynomial with the lowest possible number of terms, see A344142 and A344143.
N | The smallest n with | The corresponding polynomial of degree n
| A000120(a(n)) = N |
1 | 1 | x
3 | 2 | x^2 + x + 1
5 | 8 | x^8 + x^4 + x^3 + x + 1
7 | 37 | x^37 + x^5 + x^4 + x^3 + x^2 + x + 1
9 | 149 | x^149 + x^9 + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1
In A057496 it is stated that if x^n + x^3 + x^2 + x + 1 is irreducible, then so is x^n + x^3 + 1. It follows that no term other than 19 can be of the form 2^n + 15.

Examples

			a(8) = 283, since x^8, x^8 + 1, x^8 + x, x^8 + x + 1, ..., x^8 + x^4 + x^3 + x are all reducible over GF(2) and x^8 + x^4 + x^3 + x + 1 is irreducible, so a(8) = 2^8 + 2^4 + 2^3 + 2 + 1 = 283.
a(33) = 8589934667, since x^33, x^33 + 1, x^33 + x, x^33 + x + 1, ..., x^33 + x^6 + x^3 + x are all reducible over GF(2) and x^33 + x^6 + x^3 + x + 1 is irreducible, so a(33) = 2^33 + 2^6 + 2^3 + 2 + 1 = 8589934667. Note that there is an irreducible trinomial of degree 33, namely x^33 + x^10 + 1.

Links

Crossrefs

Cf. A014580, A344142, A344143, A000120, A057496.

Programs

  • PARI
    A344141(n) = for(k=2^n, 2^(n+1)-1, if(polisirreducible(Mod(Pol(binary(k)), 2)), return(k)))
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.