|
Search: id:A046932
|
|
|
| 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. |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.
|
|
LINKS
|
Max Alekseyev, Table of n, a(n) for n = 1..663
L. Bartholdi, Lamps, Factorizations and Finite Fields, Amer. Math. Monthly (2000), 107(5), 429-436.
International Math Olympiad, Problem 6, 1993.
Mathcad, Periodicity in Sequences Mod 3
Index entries for sequences related to trinomials over GF(2)
|
|
CROSSREFS
|
Cf. A010760, A055061, A073639, A100730, A112683.
Sequence in context: A043725 A121712 A139208 this_sequence A015821 A091711 A103007
Adjacent sequences: A046929 A046930 A046931 this_sequence 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(AT)math.ucdavis.edu)
Entry revised and b-file supplied by Max Alekseyev (maxal(AT)cs.ucsd.edu), Mar 14 2008.
|
|
|
Search completed in 0.002 seconds
|
