

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


7



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Also, the multiplicative order of x modulo the polynomial x^n + x + 1 (or its reciprocal x^n + x^(n1) + 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(i1)^2 + 2*x(i1) + 2*x(in)^2 + 2*x(in) 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(x1) XOR f(xn).
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, Deyuan Li, Ulam Sets in New Settings, arXiv:2008.02762 [math.CO], 2020.
L. Bartholdi, Lamps, Factorizations and Finite Fields, Amer. Math. Monthly (2000), 107(5), 429436.
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^m1) ) = (2^(a(k)*m)  1) / (2^m1). 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[x1] ~BitXor~ f[xn]]; ff = Array[f, 10^5]; FindTransientRepeat[ff, 2] // Last // Length]; Array[a, 15] (* JeanFranç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,changed


AUTHOR

Russell Walsmith


EXTENSIONS

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


STATUS

approved



