A073639 -id:A073639 - cp's OEIS frontend

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

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

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.

Original entry on oeis.org

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

A046932 a(n) = period of x^n + x + 1 over GF(2), i.e., the smallest integer m>0 such that x^n + x + 1 divides x^m + 1 over GF(2).

Original entry on oeis.org

1, 3, 7, 15, 21, 63, 127, 63, 73, 889, 1533, 3255, 7905, 11811, 32767, 255, 273, 253921, 413385, 761763, 5461, 4194303, 2088705, 2097151, 10961685, 298935, 125829105, 17895697, 402653181, 10845877, 2097151, 1023, 1057, 255652815, 3681400539

Offset: 1

Russell Walsmith

Also, the multiplicative order of x modulo the polynomial x^n + x + 1 (or its reciprocal x^n + x^(n-1) + 1) over GF(2).
For n>1, let S_0 = 11...1 (n times) and S_{i+1} be formed by applying D to last n bits of S_i and appending result to S_i, where D is the first difference modulo 2 (e.g., a,b,c,d,e -> a+b,b+c,c+d,d+e). The period of the resulting infinite string is a(n). E.g., n=4 produces 1111000100110101111..., so a(4) = 15.
Also, the sequence can be constructed in the same way as A112683, but using the recurrence x(i) = 2*x(i-1)^2 + 2*x(i-1) + 2*x(i-n)^2 + 2*x(i-n) mod 3.
From Ben Branman, Aug 12 2010: (Start)
Additionally, the pseudorandom binary sequence determined by the recursion
If xn, f(x)=f(x-1) XOR f(x-n).
The resulting sequence f(x) has period a(n).
For example, if n=4, then the sequence f(x) is has period 15: 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0
so a(4)=15. (End)

Max Alekseyev, Table of n, a(n) for n = 1..1223
Tej Bade, Kelly Cui, Antoine Labelle, and Deyuan Li, Ulam Sets in New Settings, arXiv:2008.02762 [math.CO], 2020. See also Integers (2020) Vol. 20, #A102.
L. Bartholdi, Lamps, Factorizations and Finite Fields, arXiv:math/9910056 [math.CO], 1999; Amer. Math. Monthly (2000), 107(5), 429-436.
Steven R. Finch, Periodicity in Sequences Mod 3 [Broken link]
Steven R. Finch, Periodicity in Sequences Mod 3 [From the Wayback machine]
International Math Olympiad, Problem 6, 1993.
Index entries for sequences related to trinomials over GF(2)

Cf. A010760, A055061, A073639, A100730, A112683.

(* This program is not suitable to compute a large number of terms. *)
a[n_] := Module[{f, ff}, f[x_] := f[x] = If[xJean-François Alcover, Sep 10 2018, after Ben Branman *)

a(n) = {pola = Mod(1,2)*(x^n+x+1); m=1; ok = 0; until (ok, polb = Mod(1,2)*(x^m+1); if (type(polb/pola) == "t_POL", ok = 1; break;); if (!ok, m++);); return (m);} \\ Michel Marcus, May 20 2013

a(2^k) = 2^(2*k) - 1.
a(2^k + 1) = 2^(2*k) + 2^k + 1.
Conjecture: a(2^k - 1) = 2^a(k) - 1. [See Bartholdi, 2000]
More general conjecture: a( (2^(k*m) - 1) / (2^m-1) ) = (2^(a(k)*m) - 1) / (2^m-1). For m=1, it would imply Bartholdi conjecture. - Max Alekseyev, Oct 21 2011

More terms from Dean Hickerson
Entry revised and b-file supplied by Max Alekseyev, Mar 14 2008
b-file extended by Max Alekseyev, Nov 15 2014; Aug 17 2015

A100729 Period of the first difference of Ulam 1-additive sequence U(2,2n+1).

Original entry on oeis.org

32, 26, 444, 1628, 5906, 80, 126960, 380882, 2097152, 1047588, 148814, 8951040, 5406720, 242, 127842440, 11419626400, 12885001946, 160159528116, 687195466408, 6390911336402, 11728121233408, 20104735604736

Offset: 2

Ralf Stephan, Dec 03 2004

nonn

It was proved by Akeran that a(2^k-1) = 3^(k+1) - 1.

Note that a(n)=2^(2n+1) as soon as A100730(n)=2^(2n+3)-2, that happens for n=(m-2)/2 with m>=6 being an even element of A073639.

			For k=2, we have a(3)=3^3-1=26.

Max Alekseyev, Table of n, a(n) for n = 2..31
M. Akeran, On some 1-additive sequences
J. Cassaigne and S. R. Finch, A class of 1-additive sequences and additive recurrences
S. R. Finch, Patterns in 1-additive sequences, Experimental Mathematics 1 (1992), 57-63.

Cf. A100730 for the fundamental difference, A001857 for U(2, 3), A007300 for U(2, 5), A003668 for U(2, 7).

Cf. also A006844.

a(3) corrected from 25 to 26 by Hugo van der Sanden and Bertram Felgenhauer (int-e(AT)gmx.de), Nov 11 2007
More terms from Balakrishnan V (balaji.iitm1(AT)gmail.com), Nov 15 2007
a(21..31) and b-file from Max Alekseyev, Dec 01 2007

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

A133485 Integers k such that the polynomial x^(2k+2) + x + 1 is primitive and irreducible over GF(2).

Original entry on oeis.org

0, 1, 2, 10, 29, 265, 449, 682

Offset: 1

Max Alekseyev, Dec 02 2007, Feb 15 2008

An integer k > 1 belongs to this sequence iff A100730(k) = 2^(2k+3) - 2.
Also, an integer k belongs to this sequence iff 2k+2 belongs to A073639.
The polynomial x^(2k+2) + x + 1 in the definition can be replaced by its reciprocal x^(2k+2) + x^(2k+1) + 1.
(2*a(n)+2) is a subsequence of A002475. - Manfred Scheucher, Aug 17 2015
a(9) >= (A002475(29) - 2)/2 = 5098.

Cf. A002475, A073639, A100730.

select(n -> (Irreduc(x^(2*n+2)+x+1) mod 2) and (Primitive(x^(2*n+2)+x+1) mod 2), [$0..500]); # Robert Israel, Aug 17 2015

polisprimitive(poli)=np = 2^poldegree(poli)-1; if (type((x^np-1)/poli) != "t_POL", return (0)); forstep(k=np-1, 1, -1, if (type((x^k-1)/poli) == "t_POL", return (0));); return(1);
lista(nn) = {for (n=0, nn, poli = Mod(1,2)*(x^(2*n+2)+x+1); if (polisirreducible(poli) && polisprimitive(poli), print1(n, ", ")););} \\ Michel Marcus, May 27 2013

def is_primitive(p):
    d = 2^(p.degree())-1
    if not p.divides(x^d-1): return False
    for k in (d//q for q in d.prime_factors()):
        if p.divides(x^k-1): return False
    return True
P. = GF(2)[]
for n in range(1,1000):
    p = x^(2*n+2)+x+1
    if p.is_irreducible() and is_primitive(p):
        print(n)
# Modification of the A002475 Script by Ruperto Corso
# Manfred Scheucher, Aug 17 2015

a(2)=1 inserted by Michel Marcus, May 29 2013

cp's OEIS Frontend

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

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

A046932 a(n) = period of x^n + x + 1 over GF(2), i.e., the smallest integer m>0 such that x^n + x + 1 divides x^m + 1 over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A100729 Period of the first difference of Ulam 1-additive sequence U(2,2n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A133485 Integers k such that the polynomial x^(2k+2) + x + 1 is primitive and irreducible over GF(2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

Sage

Extensions