|
| |
|
|
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).
|
|
5
| |
|
|
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; 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.
Contribution from Ben Branman (137ben(AT)comcast.net), 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..1025
L. Bartholdi, Lamps, Factorizations and Finite Fields, Amer. Math. Monthly (2000), 107(5), 429-436.
S. R. Finch, Periodicity in Sequences Mod 3
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]
Conjecture: a( (2^(k*m) - 1) / (2^m-1) ) = (2^(a(k)*m) - 1) / (2^m-1). [From Max Alekseyev, Oct 21 2011]
|
|
|
CROSSREFS
| Cf. A010760, A055061, A073639, A100730, A112683.
Sequence in context: A175544 A139208 A146435 * A015821 A091711 A103007
Adjacent sequences: A046929 A046930 A046931 * A046933 A046934 A046935
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Russell Walsmith (russw(AT)mailcity.com, russw(AT)lycos.com)
|
|
|
EXTENSIONS
| More terms from Dean Hickerson (dean.hickerson(AT)yahoo.com)
Entry revised and b-file supplied by Max Alekseyev (maxale(AT)gmail.com), Mar 14 2008.
|
| |
|
|
