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

From Ben Branman, 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..1223

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]

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

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

Sequence in context: A324727 A320026 A146435 * A015821 A229527 A091711

Adjacent sequences:  A046929 A046930 A046931 * A046933 A046934 A046935

KEYWORD

nonn,easy,nice

AUTHOR

Russell Walsmith

EXTENSIONS

More terms from Dean Hickerson

Entry revised and b-file supplied by Max Alekseyev, Mar 14 2008

b-file extended by Max Alekseyev, Nov 15 2014; Aug 17 2015

STATUS

approved

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 March 26 14:18 EDT 2019. Contains 321497 sequences. (Running on oeis4.)