A001153 -id:A001153 - cp's OEIS frontend

A074743 Smallest k such that trinomial x^A001153(n) + x^k + 1 over GF(2) is primitive.

1, 1, 2, 1, 3, 3, 38, 1, 32, 105, 216, 715, 67, 271, 84, 881, 1530, 8575, 25230, 7000, 215747, 170340, 361604, 3037958, 8412642, 880890, 2162059, 5110722, 55981, 3569337

Offset: 1

N. J. A. Sloane, Sep 06 2002

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 p. 162.
Index entries for sequences related to trinomials over GF(2)

for n from 1 to 16 do for k from 1 to A001153(n)-1 do if(Primitive(x^A001153(n) + x^k + 1) mod 2)then printf("%d, ",k): break: fi:od:od: # Nathaniel Johnston, Apr 21 2011

a(8)-a(16) from Nathaniel Johnston, Apr 21 2011

a(17)-a(30) from Brent's data added by Max Alekseyev, Oct 22 2011

A002475 Numbers k such that x^k + x + 1 is irreducible over GF(2).

Original entry on oeis.org

0, 2, 3, 4, 6, 7, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900, 1366, 2380, 3310, 4495, 6321, 7447, 10198, 11425, 21846, 24369, 27286, 28713, 32767, 34353, 46383, 53484, 62481, 83406, 87382, 103468, 198958, 248833

Offset: 1

N. J. A. Sloane

k=1 is excluded since the polynomial "1" is not normally regarded as irreducible.
2^(A073639(m)) - 1 is a term for all m. - Joerg Arndt, Aug 23 2015
Any subsequent terms are > 300000. - Lucas A. Brown, Nov 28 2022

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).
Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 975.

Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
Lucas A. Brown, Python program.
Lucas A. Brown, Sage program.
N. Zierler, On x^n+x+1 over GF(2), Information and Control, 16 1970 502-505.
Index entries for sequences related to trinomials over GF(2)

Cf. A001153, A073639, A057496, A223938 (n such that x^n-x-1 is irreducible over GF(3)).

P := PolynomialRing(GaloisField(2)); for n := 0 to 100000 do if IsIrreducible(x^n+x+1) then print(n); end if; end for;

select(n -> Irreduc(x^n+x+1) mod 2, [0,$2..10000]); # Robert Israel, Aug 09 2015

Do[ If[ ToString[ Factor[ x^n + x + 1, Modulus -> 2 ] ] == ToString[ x^n + x + 1 ], Print [ n ] ], {n, 0, 28713} ]
Select[Range[1000], IrreduciblePolynomialQ[x^# + x + 1, Modulus -> 2] &] (* Robert Price, Sep 19 2018 *)

for (n=1,10^6, if ( polisirreducible(Mod(1,2)*(x^n+x+1)), print1(n,", ") ) );
/* Joerg Arndt, Apr 28 2012 */

is(n)=if(n>3&&[1,0,1,1,0,1,0,0][n%8+1], return(0)); polisirreducible(Mod('x^n+'x+1,2)) \\ Charles R Greathouse IV, Jun 04 2015

P. = GF(2)[]
for n in range(90):
       if (x^n+x+1).is_irreducible():
           print(n) # Ruperto Corso, Dec 11 2011

Two more terms from Paul Zimmermann, Sep 05 2002
a(37)-a(39) from Max Alekseyev, Oct 29 2011
a(40)-a(41) from Ruperto Corso, Dec 11 2011
a(42) from Manfred Scheucher, Jun 04 2015
a(43) from Manfred Scheucher, Aug 09 2015
a(44) from Lucas A. Brown, Nov 28 2022

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.

Original entry on oeis.org

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

Offset: 1

Paul Zimmermann, Sep 05 2002

nonn

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.

S. W. Golomb, "Shift register sequence", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.

Joerg Arndt, Table of n, a(n) for n = 1..1500
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.6.
Index entries for sequences related to trinomials over GF(2)

For the numbers of such trinomials for a given n, see A057646.

See A073726 for primitive trinomials and A001153 for primitive Mersenne trinomials (and references). Complement of A057486. For values of k see A057774.

a := proc(n) local k; for k from 1 to n-1 do if Irreduc(x^n+x^k+1) mod 2 then RETURN(n) fi od; NULL end: [seq(a(n), n=1..130)];

irreducibleQ[n_] := (irr = False; k = 1; While[k < n, If[ Factor[ x^n + x^k + 1, Modulus -> 2] == x^n + x^k + 1, irr = True; Break[]]; k++]; irr); Select[ Range[120], irreducibleQ] (* Jean-François Alcover, Jan 07 2013 *)

is(n)=for(s=1,n-1,if(polisirreducible((x^n+x^s+1)*Mod(1,2)), return(1)));0 \\ Charles R Greathouse IV, May 30 2013

A073726 Primitive irreducible trinomials: x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n.

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, 140, 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

Richard P. Brent and Paul Zimmermann, Sep 05 2002

Start is similar to A194125; first terms here but missing there are 140, 212, 236.

S. W. Golomb, "Shift Register Sequences", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.

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]
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.8.
Index entries for sequences related to trinomials over GF(2)

See A073571 for irreducible trinomials and A001153 for primitive Mersenne trinomials (and references). See A074744 for values of k.

Cf. A194125 (n such that x^n+(1+x)^w over GF(2) is primitive for some w).

A073726 := function(n) for k := 1 to n-1 do if IsPrimitive(x^n+x^k+1) then return true; end if; end for; return false; end function; l := []; for n := 1 to 100 do if A073726(n) then l := Append(l,n); end if; end for; l;

A073726 := proc(n) local k,m: option remember: if(n=1)then return 2: else m:=procname(n-1)+1: while(true)do for k from 1 to m-1 do if Primitive(x^m+x^k+1) mod 2 then return m: fi: od: m:=m+1: od: fi: end:
seq(A073726(n),n=1..20); # Nathaniel Johnston, Apr 26 2011

okQ[n_] := AnyTrue[Range[n-1], PrimitivePolynomialQ[x^n + x^# + 1, 2]&];
Select[Range[201], okQ] (* Jean-François Alcover, Aug 19 2019 *)

a(49)-a(58) from Nathaniel Johnston, Apr 26 2011

A057486 Numbers k such that x^k + x^m + 1 is factorable over GF(2) for all m between 1 and k.

Original entry on oeis.org

8, 13, 16, 19, 24, 26, 27, 32, 37, 38, 40, 43, 45, 48, 50, 51, 53, 56, 59, 61, 64, 67, 69, 70, 72, 75, 77, 78, 80, 82, 83, 85, 88, 91, 96, 99, 101, 104, 107, 109, 112, 114, 115, 116, 117, 120, 122, 125, 128, 131, 133, 136, 138, 139, 141, 143, 144, 149, 152, 157

Offset: 1

Robert G. Wilson v, Sep 28 2000

nonn

Brent, Hart, Kruppa, and Zimmermann found that 57885161 is a term of this sequence. - Charles R Greathouse IV, May 30 2013

			a(1) = 8 because
x^8 + x^1 + 1 = (1 + x + x^2)*(1 + x^2 + x^3 + x^5 + x^6),
x^8 + x^2 + 1 = (1 + x + x^4)^2,
x^8 + x^3 + 1 = (1 + x + x^3)*(1 + x + x^2 + x^3 + x^5),
x^8 + x^4 + 1 = (1 + x + x^2)^4,
x^8 + x^5 + 1 = (1 + x^2 + x^3)*(1 + x^2 + x^3 + x^4 + x^5),
x^8 + x^6 + 1 = (1 + x^3 + x^4)^2, and
x^8 + x^7 + 1 = (1 + x + x^2)*(1 + x + x^3 + x^4 + x^6).

Charles R Greathouse IV, Table of n, a(n) for n = 1..5000 (first 200 terms from T. D. Noe)
Richard Brent, The Software gf2x.
Paul Zimmermann, There is no primitive trinomial of degree 57885161 over GF(2), posting to NMBRTHRY mailing list [alternate link]
Index entries for sequences related to trinomials over GF(2)

Complement of A073571. Cf. A001153, A002475, A073639.

Do[ k = 1; While[ ToString[ Factor[ x^n + x^k + 1, Modulus -> 2 ]] != ToString[ x^n + x^k + 1 ] && k < n, k++ ]; If[ k == n, Print[ n ]], {n, 2, 234} ]

is(n)=for(s=1,n\2,if(polisirreducible((x^n+x^s+1)*Mod(1,2)), return(0)));1 \\ Charles R Greathouse IV, May 30 2013

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

A291855 Numbers k such that gpf(2^k - 1) - 1 is not divisible by k.

Original entry on oeis.org

28, 52, 68, 92, 124, 156, 172, 244, 260, 308, 327, 340, 348, 356, 380, 396, 404, 428, 436, 500, 508, 516, 532, 580, 612, 644, 660, 684, 696, 724, 732, 748, 764, 780, 796, 820, 836, 908, 940, 980, 996, 1056, 1076, 1124, 1172, 1180

Offset: 1

Thomas Ordowski and Altug Alkan, Sep 04 2017

nonn

For a(n) <= 10^3, all terms are divisible by 4 except 327 = 3*109.
Primes p such that 4*p is a term are 7, 13, 17, 23, 31, 43, 61, ...
From Thomas Ordowski, Sep 04 2017: (Start)
If p == +-1 (mod 8) and 2^p - 1 is prime, then 4*p is a term.
Conjecture: 4 * A001153(m) for m > 3 is a subsequence.
Primes q such that q-1 is a term are 29, 53, 157, 173, 349, 397, ... (End)

			28 is a term because gpf(2^28 - 1) == 15 (mod 28).

Cf. A000225, A005420, A006530.

Subsequence of A292199.

a(10)-a(41) from Giovanni Resta, Sep 04 2017

a(42)-a(46) from Max Alekseyev, Sep 13 2017

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

cp's OEIS Frontend

A074743 Smallest k such that trinomial x^A001153(n) + x^k + 1 over GF(2) is primitive.

Views

Author

Keywords

Links

Programs

Maple

Extensions

A002475 Numbers k such that x^k + x + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

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

A073726 Primitive irreducible trinomials: x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Extensions

A057486 Numbers k such that x^k + x^m + 1 is factorable over GF(2) for all m between 1 and k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

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