A057461 -id:A057461 - cp's OEIS frontend

A057496 Numbers n such that x^n + x^3 + x^2 + x + 1 is irreducible over GF(2).

1, 2, 3, 4, 5, 7, 10, 17, 20, 25, 28, 31, 41, 52, 130, 151, 196, 503, 650, 761, 986, 1391, 2047, 6172, 6431, 6730, 8425, 10162, 11410, 12071, 13151, 14636, 17377, 18023, 32770, 77047, 102842, 130777, 137113, 143503, 168812, 192076

Offset: 1

Robert G. Wilson v, Sep 27 2000

nonn

If x^n + x^3 + x^2 + x + 1 is irreducible, then so is its "twin" x^n + x^3 + 1. - Gove Effinger, Mar 11 2007

No term other than 3 can be a multiple of 3, since for m > 1, x^(3*m) + x^3 + x^2 + x + 1 is divisible by x^2 + x + 1. - Jianing Song, May 11 2021

Cf. A002475.

Other than the term 3, subsequence of A057461.

Using probabilistic arguments it appears that there should be about 6.5 terms in this sequence with any given number of decimal digits d. - Gove Effinger, Mar 11 2007

a(20)-a(23) from Robert G. Wilson v, Mar 11 2007
a(24)-a(27) computed by Richard P. Brent, Mar 11 2007, communicated by Gove Effinger
a(27)-a(35) computed by Richard P. Brent, Mar 16 2007, communicated by Gove Effinger
a(36)-a(42) computed by Jonathan Webster, Feb 18 2010
Added entries a(1), a(2), a(3) since x^3 + x^2 + 1, x^3 + x + 1 and x^2 + x + 1 are irreducible over GF(2). Changed the offset for the entries computed by Robert G. Wilson v and Richard P. Brent to account for this. Added terms a(36) through a(42). - Jonathan Webster (jwebster(AT)bates.edu), Feb 18 2010

A344177 Numbers m > 3 such that x^m + x^3 + 1 is irreducible over GF(2) while x^m + x^3 + x^2 + x + 1 = x^m + (x + 1)^3 is not.

Original entry on oeis.org

6, 12, 18, 66, 180, 1596, 2700, 4098, 30594, 65538

Offset: 1

Jianing Song, May 11 2021

Numbers m >= 4 that are in A057461 but not in A057496.
In A057496 it is stated that if x^m + x^3 + x^2 + x + 1 is irreducible, then so is x^m + x^3 + 1. It seems that if x^m + x^3 + 1 is irreducible and m is not a multiple of 6, then so is x^m + x^3 + x^2 + x + 1. In other words, it seems that this sequence consists of the terms in A057461 that are multiples of 6.
Conjecture: Given e >= 0, odd numbers r, k > 0, a > 2^e*r*k, consider the following two statements:
(A) x^m + (x^k + 1)^(2^e*r) is irreducible over GF(2);
(B) x^m + x^(2^e*r*k) + 1 is irreducible over GF(2),
then:
(i) (A) implies (B);
(ii) if (B) is true and (A) is false, then:
    (a) gcd(m,r) > 1;
    (b) if prime p | gcd(m,r*k), then p*ord_p(2) | m;
    (c) if e > 0, then m is odd.
Here ord(2,p) is the multiplicative order of 2 modulo p.
In other words, assuming that (B) is true, (A) is false if and only if (a), (b), (c) hold. (For the "if" part, note that if d = gcd(m,2^e*r) > 1 then x^m + (x^k + 1)^(2^e*r) must be reducible, since it is divisible by x^(m/d) + (x^k + 1)^(2^e*r/d).)
Here is the case r = 3, k = 1, e = 0, and (ii) means that m is in this sequence if and only if x^m + x^3 + 1 is irreducible and m is a multiple of 6.

			18 is a term because x^18 + x^3 + 1 is irreducible over GF(2) but x^18 + x^3 + x^2 + x + 1 is not: x^18 + x^3 + x^2 + x + 1 = (x^2 + x + 1)*(x^6 + x + 1)*(x^10 + x^9 + x^7 + x^6 + x^5 + x^4 + x^2 + x + 1).

Cf. A057461, A057496.

Similar sequences: this sequence (r=3, k=1), A344198 (r=3, k=3), A344199 (r=3, k=5), A344197 (r=5, k=1), A344200 (r=5, k=3).

isA344177(n) = polisirreducible(Mod(x^n+x^3+1, 2)) && !polisirreducible(Mod(x^n+x^3+x^2+x+1, 2))

A278572 Irregular triangle read by rows: row n lists values of k in range 1 <= k <= n/2 such x^n + x^k + 1 is irreducible (mod 2), or -1 if no such k exists.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 3, -1, 1, 4, 3, 2, 3, 5, -1, 5, 1, 4, 7, -1, 3, 5, 6, 3, 7, 9, -1, 3, 5, 2, 7, 1, 5, 9, -1, 3, 7, -1, -1, 1, 3, 9, 13, 2, 1, 9, 3, 6, 7, 13, -1, 10, 13, 7, 2, 9, 11, 15, -1, -1, 4, 8, 14, -1, 3, 20, 7, -1, 5, -1, 1, 5, 14, 20, 21, -1

Offset: 2

N. J. A. Sloane, Nov 27 2016

This is the format used by John Brillhart (1968) and Zierler and Brillhart (1968).

			Triangle begins:
1,
1,
1,
2,
1, 3,
1, 3,
-1,
1, 4,
3,
2,
3, 5,
-1,
5,
1, 4, 7,
-1,
3, 5, 6,
...

Alanen, J. D., and Donald E. Knuth. "Tables of finite fields." Sankhyā: The Indian Journal of Statistics, Series A (1964): 305-328.
John Brillhart, On primitive trinomials (mod 2), unpublished Bell Labs Memorandum, 1968.
Marsh, Richard W. Table of irreducible polynomials over GF (2) through degree 19. Office of Technical Services, US Department of Commerce, 1957.

Robert Israel, Table of n, a(n) for n = 2..4328 (rows 2 to 2170, flattened)
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400. (Lists primitive trinomials only.)
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400 [Cached copy, with permission]
R. P. Brent, Trinomial Log Files and Certificates
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.6.
Svein Mossige, Table of irreducible polynomials over GF[2] of degrees 10 through 20, Mathematics of Computation 26.120 (1972): 1007-1009.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541-554.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566-569.
Index entries for sequences related to trinomials over GF(2)

Cf. A001153, A057646, A057774, A073571, A073646, A073726, A074743, A278573.

Rows n that contain particular numbers: 1 (A002475), 2 (A057460), 3 (A057461), 4 (A057463), 5 (A057474), 6 (A057476), 7 (A057477), 8 (A057478), 9 (A057479), 10 (A057480), 11 (A057481), 12 (A057482), 13 (A057483).

T:= proc(n) local L; L:= select(k -> Irreduc(x^n+x^k+1) mod 2, [$1..n/2]); if L = [] then -1 else op(L) fi
end proc:
map(T, [$2..100]); # Robert Israel, Mar 28 2017

DeleteCases[#, 0] & /@ Table[Boole[IrreduciblePolynomialQ[x^n + x^# + 1, Modulus -> 2]] # & /@ Range[Floor[n/2]], {n, 2, 40}] /. {} -> {-1} // Flatten (* Michael De Vlieger, Mar 28 2017 *)

cp's OEIS Frontend

A057496 Numbers n such that x^n + x^3 + x^2 + x + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A344177 Numbers m > 3 such that x^m + x^3 + 1 is irreducible over GF(2) while x^m + x^3 + x^2 + x + 1 = x^m + (x + 1)^3 is not.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A278572 Irregular triangle read by rows: row n lists values of k in range 1 <= k <= n/2 such x^n + x^k + 1 is irreducible (mod 2), or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A058236 Numbers n such that x^n + x^3 + 2 is irreducible over GF(3).

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions