A073726 -id:A073726 - cp's OEIS frontend

A001153 Degrees of primitive irreducible trinomials: n such that 2^n - 1 is a Mersenne prime and x^n + x^k + 1 is a primitive irreducible polynomial over GF(2) for some k with 0 < k < n.

2, 3, 5, 7, 17, 31, 89, 127, 521, 607, 1279, 2281, 3217, 4423, 9689, 19937, 23209, 44497, 110503, 132049, 756839, 859433, 3021377, 6972593, 24036583, 25964951, 30402457, 32582657, 42643801, 43112609

Offset: 1

N. J. A. Sloane

Also the list of "irreducible Mersenne trinomials" since here irreducible implies primitive.
Further terms of the form +-3 (mod 8) are unlikely, as the only possibility of an irreducible trinomial for n == +-3 (mod 8) is (by Swan's theorem) x^n+x^2+1 (and its reciprocal); see the Ciet et al. and the Swan reference. - Joerg Arndt, Jan 06 2014
The first Mersenne prime exponent not ruled out by Swan's theorem and yet not a member of this sequence is 57885161. - Gord Palameta, Jul 20 2018
74207281 is also in the sequence. - Gord Palameta, Jul 20 2018

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Joerg Arndt, Matters Computational (The Fxtbook), see p.850 (but note errata for statement of Swan's theorem).
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400.
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400 [Cached copy, with permission]
R. P. Brent, Searching for primitive trinomials (mod 2) (first, "old" page)
R. P. Brent, Searching for primitive trinomials (mod 2) (second, current page)
R. P. Brent, Trinomial Log Files and Certificates
Richard P. Brent and Paul Zimmerman, Twelve New Primitive Binary Trinomials, HAL Id : hal-01378493.
R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 1443-1452.
Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica, A Short Note on Irreducible Trinomials in Binary Fields, in: 23rd Symposium on Information Theory in the BENELUX, Louvain-la-Neuve, Belgium, Macq, B., Quisquater, J.-J. (eds.), pp.233-234, (May-2002).
Yoshiharu Kurita and Makoto Matsumoto, Primitive t-nomials (t=3,5) over GF(2) whose degree is a Mersenne exponent <= 44497, Math. Comp. 56 (1991), no. 194, 817-821.
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see p. 162.
Richard G. Swan, Factorization of polynomials over finite fields, Pacific Journal of Mathematics, vol.12, no.3, pp.1099-1106, (1962).
N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 67-69.
N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502-505.
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. A002475, A000043, A073571, A073639, A057486, A073726.

For smallest values of k, see A074743.

Corrected and extended by Paul Zimmermann, Sep 05 2002

Six more terms from Brent's page added by Max Alekseyev, Oct 22 2011

A132454 First primitive GF(2)[X] polynomials of degree n and minimal number of terms, expressed as -k for X^n+X^k+1, else with X^n suppressed.

Original entry on oeis.org

1, -1, -1, -1, -2, -1, -1, 29, -4, -3, -2, 83, 27, 43, -1, 45, -3, -7, 39, -3, -2, -1, -5, 27, -3, 71, 39, -3, -2, 83, -3, 197, -13, 281, -2, -11, 83

Offset: 1

Francois R. Grieu, Aug 22 2007

More precisely: when there exists k, 0

			a(10)=-3, representing the GF(2)[X] polynomial X^10+X^3+1, because this degree 10 trinomial is primitive, contrary to X^10+X^1+1, X^10+X^2+1 and X^10+X^2+X^1.

Either of 2^n+2^(-a(n))+1 or 2^n+a(n) belongs to A091250. If there exists m such that n = A073726(m), then a(n) = -A074744(m); otherwise a(n) = A132450(n). A132453(n) gives the primitive polynomial corresponding to a(n). Cf. A132448, similar, with no restriction on number of terms. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132452, similar, with restriction to exactly 5 terms.

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 *)

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

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 3, 1, 3, 5, 1, 3, 4, 6, -1, 1, 4, 5, 8, 3, 7, 2, 9, 3, 5, 7, 9, -1, 5, 9, 1, 4, 7, 8, 11, 14, -1, 3, 5, 6, 11, 12, 14, 3, 7, 9, 11, 15, -1, 3, 5, 15, 17, 2, 7, 14, 19, 1, 21, 5, 9, 14, 18, -1, 3, 7, 18, 22, -1, -1, 1, 3, 9, 13, 15, 19, 25, 27, 2, 27, 1, 9, 21, 29, 3, 6, 7, 13

Offset: 2

N. J. A. Sloane, Nov 27 2016

Row n (if it is not -1) is invariant under the map k -> n-k. - Robert Israel, Mar 14 2018

			Triangle begins:
1,
1, 2,
1, 3,
2, 3,
1, 3, 5,
1, 3, 4, 6,
-1,
1, 4, 5, 8,
3, 7,
2, 9,
3, 5, 7, 9,
-1,
5, 9,
1, 4, 7, 8, 11, 14,
-1,
3, 5, 6, 11, 12, 14,
3, 7, 9, 11, 15,
-1,
3, 5, 15, 17,
2, 7, 14, 19,
1, 21,
...

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..4558 (rows 2 to 1300, 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, A278572.

for n from 2 to 30 do
  S:= select(k -> Irreduc(x^n+x^k+1) mod 2, [$1..n-1]);
  if S = [] then print(-1) else print(op(S)) fi
od: # Robert Israel, Mar 14 2018

A136416 Numbers n such that 1+(x+1)^k+(x+1)^n is a primitive polynomial over GF(2) for some k where 0

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 15, 17, 18, 20, 21, 22, 23, 25, 28, 29, 31, 33, 35, 36, 39, 41, 42, 47, 49, 52, 54, 55, 57, 58, 60, 62, 63, 65, 66, 68, 71, 73, 74, 76, 79, 81, 84, 86, 87, 89, 92, 93, 94, 95, 97, 98, 100, 102, 103, 105, 106, 108, 110, 111, 113, 118, 119, 121

Offset: 1

Joerg Arndt, Mar 31 2008, May 02 2009

nonn

Iff the trinomial T(x)=1+x^k+x^n is irreducible (A073571) then the polynomial T(x+1)=1+(x+1)^k+(1+x)^n is irreducible.
The order of T(x+1) is in general different from the order of T(x).
So this sequence is different from A073726: for example, 1+(x+1)^7+(1+x)^10 is primitive but 1+(x+1)^3+(1+x)^10 is not (while 1+x^7+x^10 and 1+x^3+x^10 are mutual reciprocal and have the same order).

			10 is in the sequence because 1+(x+1)^7+(1+x)^10 is a primitive polynomial over GF(2).

Joerg Arndt, Mar 31 2008, Table of n, a(n) for n = 1..211
Joerg Arndt, Matters Computational (The Fxtbook)

A194125 n such that a length-n CLHCA of maximal period exists.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 9, 10, 11, 15, 17, 18, 20, 21, 22, 23, 25, 28, 29, 31, 33, 35, 36, 39, 41, 47, 49, 52, 55, 57, 58, 60, 63, 65, 68, 71, 73, 79, 81, 84, 87, 89, 93, 94, 95, 97, 98, 100, 103, 105, 106, 108, 111, 113, 118, 119, 121, 123, 124, 127, 129, 130, 132, 134, 135, 137, 142, 145, 148, 150, 151, 153, 159, 161, 167, 169, 170, 172, 174, 175, 177, 178, 183, 185, 191, 193, 194, 198, 199, 201

Offset: 1

Joerg Arndt, Aug 15 2011

nonn

A CLHCA is a cyclic linear hybrid cellular automaton (defined on p.883 of the Fxtbook, see link below). For fixed n its period depends only on the weight of its rule vector. The polynomial corresponding to a weight-w length-n CLHCA is x^n+(1+x)^w (or its reciprocal polynomial 1+x^w*(1+x)^(n-w)).

Sequence starts as A073726 (and appears to be a subset), first terms missing in this one are 140, 212, 236 (and no more <= 400).

Joerg Arndt, Matters Computational (The Fxtbook), section 41.9.1, pp. 883-885
Joerg Arndt, Rules for CLHCA with maximal period up to degree 400, Complete list of primitive trinomials over GF(2) up to degree 400.
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400 [Cached copy, with permission]

Cf. A073726 (n such that a primitive trinomial over GF(2) exists).

A283091 Maximal order of the trinomials of degree n over GF(2).

Original entry on oeis.org

3, 7, 15, 31, 63, 127, 217, 511, 1023, 2047, 3255, 8001, 11811, 32767, 63457, 131071, 262143, 520065, 1048575, 2097151, 4194303, 8388607, 16766977, 33554431, 67074049, 133693185, 268435455, 536870911, 1073215489, 2147483647, 4292868097, 8589934591, 17179312129

Offset: 2

Charles R Greathouse IV, Feb 28 2017

nonn

a(n) is also the maximum length of binary linear recurrence relation b(x) = b(x-m) + b(x-n) mod 2 for all 0 < m < n. Knuth cites unpublished work of G. J. Mitchell & D. P. Moore showing that a(55) = 2^55 - 1 via m = 24.

D. E. Knuth, The Art of Computer Programming. Vol. 2, Seminumerical Algorithms.

Hiroaki Yamanouchi, Table of n, a(n) for n = 2..100
Index entries for sequences related to pseudo-random numbers.

Cf. A073726.

isperiodic(v)=for(k=1,#v-3, for(i=k+1,#v, if(v[i]!=v[i-k], next(2))); return(k))
T(n,m,len=2^n+7)=my(v=vectorsmall(len)); v[n]=1; for(k=n+1,#v, v[k]=(v[k-n]+v[k-m])%2); v=isperiodic(v); if(v,v,T(n,m,2*len+1))
a(n)=my(mx=T(n,1)); for(m=2,n-1,mx=max(T(n,m),mx)); mx

a(n) <= 2^n - 1, with equality if and only if n is a term of A073726.

a(26)-a(34) from Hiroaki Yamanouchi, Apr 06 2017

Showing 1-10 of 10 results.

This sequence is infinite: Golomb, "Shift Register Sequences," on p. 96 (1st ed., 1966) states that "It is easy to exhibit an infinite class of irreducible trinomials. viz. x^(2*3^a) + x^(3^a) + 1 for all a = 0, 1, 2, ..., but whose roots have only 3^(a+1) as their period." - A. M. Odlyzko, Dec 05 1997.

cp's OEIS Frontend

A074744 Values of k corresponding to A073726.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Extensions

A186440 Number of prime divisors (counted with multiplicity) of n such that the primitive irreducible trinomial x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n (A073726).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A073571 Irreducible trinomials: numbers n such that x^n + x^k + 1 is an irreducible polynomial (mod 2) for some k with 0 < k < n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A001153 Degrees of primitive irreducible trinomials: n such that 2^n - 1 is a Mersenne prime and x^n + x^k + 1 is a primitive irreducible polynomial over GF(2) for some k with 0 < k < n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A132454 First primitive GF(2)[X] polynomials of degree n and minimal number of terms, expressed as -k for X^n+X^k+1, else with X^n suppressed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A278573 Irregular triangle read by rows: row n lists values of k in range 1 <= k <= n-1 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

A136416 Numbers n such that 1+(x+1)^k+(x+1)^n is a primitive polynomial over GF(2) for some k where 0

Views

Author

Keywords

Comments

Examples

Links

A194125 n such that a length-n CLHCA of maximal period exists.

Views