A283091 Maximal order of the trinomials of degree n over GF(2).

3, 7, 15, 31, 63, 127, 217, 511, 1023, 2047, 3255, 8001, 11811, 32767, 63457, 131071, 262143, 520065, 1048575, 2097151, 4194303, 8388607, 16766977, 33554431, 67074049, 133693185, 268435455, 536870911, 1073215489, 2147483647, 4292868097, 8589934591, 17179312129

Offset

2,1

Comments

a(n) is also the maximum length of binary linear recurrence relation b(x) = b(x-m) + b(x-n) mod 2 for all 0 < m < n. Knuth cites unpublished work of G. J. Mitchell & D. P. Moore showing that a(55) = 2^55 - 1 via m = 24.

References

D. E. Knuth, The Art of Computer Programming. Vol. 2, Seminumerical Algorithms.

Links

Hiroaki Yamanouchi, Table of n, a(n) for n = 2..100

Index entries for sequences related to pseudo-random numbers.

Formula

a(n) <= 2^n - 1, with equality if and only if n is a term of A073726.

Prog

(PARI) isperiodic(v)=for(k=1, #v-3, for(i=k+1, #v, if(v[i]!=v[i-k], next(2))); return(k))
T(n, m, len=2^n+7)=my(v=vectorsmall(len)); v[n]=1; for(k=n+1, #v, v[k]=(v[k-n]+v[k-m])%2); v=isperiodic(v); if(v, v, T(n, m, 2*len+1))
a(n)=my(mx=T(n, 1)); for(m=2, n-1, mx=max(T(n, m), mx)); mx

Crossrefs

Cf. A073726.

Sequence in context: A273672 A043740 A336683 * A277716 A116082 A245269

Adjacent sequences: A283088 A283089 A283090 * A283092 A283093 A283094

Keyword

nonn

Author

Charles R Greathouse IV, Feb 28 2017

Extensions

a(26)-a(34) from Hiroaki Yamanouchi, Apr 06 2017

Status

approved