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

Author

Russell Walsmith

Keywords

• nonn
• easy
• nice

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

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

Crossrefs

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

Programs

Mathematica

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

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

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

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