The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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^(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, 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), 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. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 20 12:27 EDT 2020. Contains 337904 sequences. (Running on oeis4.)