cp's OEIS Frontend

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

%I A046932 #80 May 01 2025 01:35:51
%S A046932 1,3,7,15,21,63,127,63,73,889,1533,3255,7905,11811,32767,255,273,
%T A046932 253921,413385,761763,5461,4194303,2088705,2097151,10961685,298935,
%U A046932 125829105,17895697,402653181,10845877,2097151,1023,1057,255652815,3681400539
%N 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).
%C A046932 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 A046932 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 A046932 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 A046932 From _Ben Branman_, Aug 12 2010: (Start)
%C A046932 Additionally, the pseudorandom binary sequence determined by the recursion
%C A046932 If x<n+1, then f(x)=1. If x>n, f(x)=f(x-1) XOR f(x-n).
%C A046932 The resulting sequence f(x) has period a(n).
%C A046932 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 A046932 so a(4)=15. (End)
%H A046932 Max Alekseyev, <a href="/A046932/b046932.txt">Table of n, a(n) for n = 1..1223</a>
%H A046932 Tej Bade, Kelly Cui, Antoine Labelle, and Deyuan Li, <a href="https://arxiv.org/abs/2008.02762">Ulam Sets in New Settings</a>, arXiv:2008.02762 [math.CO], 2020. See also <a href="https://math.colgate.edu/~integers/u102/u102.pdf">Integers</a> (2020) Vol. 20, #A102.
%H A046932 L. Bartholdi, <a href="https://arxiv.org/abs/math/9910056">Lamps, Factorizations and Finite Fields</a>, arXiv:math/9910056 [math.CO], 1999; Amer. Math. Monthly (2000), 107(5), 429-436.
%H A046932 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/seqmod3.pdf">Periodicity in Sequences Mod 3</a> [Broken link]
%H A046932 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 A046932 International Math Olympiad, <a href="https://artofproblemsolving.com/community/c6h62190">Problem 6, 1993</a>.
%H A046932 <a href="/index/Tri#trinomial">Index entries for sequences related to trinomials over GF(2)</a>
%F A046932 a(2^k) = 2^(2*k) - 1.
%F A046932 a(2^k + 1) = 2^(2*k) + 2^k + 1.
%F A046932 Conjecture: a(2^k - 1) = 2^a(k) - 1. [See Bartholdi, 2000]
%F A046932 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 A046932 (* This program is not suitable to compute a large number of terms. *)
%t A046932 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 A046932 (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 A046932 Cf. A010760, A055061, A073639, A100730, A112683.
%K A046932 nonn,easy,nice
%O A046932 1,2
%A A046932 _Russell Walsmith_
%E A046932 More terms from _Dean Hickerson_
%E A046932 Entry revised and b-file supplied by _Max Alekseyev_, Mar 14 2008
%E A046932 b-file extended by _Max Alekseyev_, Nov 15 2014; Aug 17 2015