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

Author

Charles R Greathouse IV, Feb 28 2017

Keywords

• nonn

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.

Crossrefs

Cf. A073726.

Programs

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

Formula

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

Extensions

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