login
A283091
Maximal order of the trinomials of degree n over GF(2).
1
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.
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
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(26)-a(34) from Hiroaki Yamanouchi, Apr 06 2017
STATUS
approved