login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I

%S 1,3,7,15,21,63,127,63,73,889,1533,3255,7905,11811,32767,255,273,

%T 253921,413385,761763,5461,4194303,2088705,2097151,10961685,298935,

%U 125829105,17895697,402653181,10845877,2097151,1023,1057,255652815,3681400539

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

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

%C 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.

%C 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.

%C From _Ben Branman_, Aug 12 2010: (Start)

%C Additionally, the pseudorandom binary sequence determined by the recursion

%C If x<n+1, then f(x)=1. If x>n, f(x)=f(x-1) XOR f(x-n).

%C The resulting sequence f(x) has period a(n).

%C 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

%C so a(4)=15. (End)

%H Max Alekseyev, <a href="/A046932/b046932.txt">Table of n, a(n) for n = 1..1223</a>

%H L. Bartholdi, <a href="http://arXiv.org/abs/math.CO/9910056">Lamps, Factorizations and Finite Fields</a>, Amer. Math. Monthly (2000), 107(5), 429-436.

%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/seqmod3.pdf">Periodicity in Sequences Mod 3</a> [Broken link]

%H Steven R. Finch, <a href="https://web.archive.org/web/20150911081920/http://www.people.fas.harvard.edu/~sfinch/csolve/seqmod3.pdf">Periodicity in Sequences Mod 3</a> [From the Wayback machine]

%H International Math Olympiad, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?t=62190">Problem 6, 1993</a>.

%H <a href="/index/Tri#trinomial">Index entries for sequences related to trinomials over GF(2)</a>

%F a(2^k) = 2^(2*k) - 1.

%F a(2^k + 1) = 2^(2*k) + 2^k + 1.

%F Conjecture: a(2^k - 1) = 2^a(k) - 1. [See Bartholdi, 2000]

%F 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

%t (* This program is not suitable to compute a large number of terms. *)

%t 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_ *)

%o (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

%Y Cf. A010760, A055061, A073639, A100730, A112683.

%K nonn,easy,nice

%O 1,2

%A _Russell Walsmith_

%E More terms from _Dean Hickerson_

%E Entry revised and b-file supplied by _Max Alekseyev_, Mar 14 2008

%E b-file extended by _Max Alekseyev_, Nov 15 2014; Aug 17 2015

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 09:03 EST 2019. Contains 329144 sequences. (Running on oeis4.)