|
| |
|
|
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).
|
|
8
|
|
|
|
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.
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
