A283091 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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