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

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

Comments

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 x<n+1, then f(x)=1. If x>n, 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)

Links

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

Formula

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

Mathematica

(* This program is not suitable to compute a large number of terms. *)
a[n_] := Module[{f, ff}, f[x_] := f[x] = If[x<n+1, 1, f[x-1] ~BitXor~ f[x-n]]; ff = Array[f, 10^5]; FindTransientRepeat[ff, 2] // Last // Length]; Array[a, 15] (* Jean-François Alcover, Sep 10 2018, after Ben Branman *)

Prog

(PARI) 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

Crossrefs

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

Sequence in context: A324727 A320026 A146435 * A015821 A229527 A091711

Adjacent sequences: A046929 A046930 A046931 * A046933 A046934 A046935

Keyword

nonn,easy,nice

Author

Russell Walsmith

Extensions

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

Status

approved