|
| |
|
|
A217990
|
|
Size of largest semigroup generated by one Boolean n X n matrix.
|
|
1
|
|
|
|
1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 420
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
J. Denes, K. H. Kim, and F. W. Roush, Automata on one symbol, in Studies in Pure Mathematics: To the Memory of Paul Turan, Birkhauser, 1983, pp. 127-134.
|
|
|
LINKS
|
Table of n, a(n) for n=1..19.
George Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum 13 (1977), 253-259.
|
|
|
FORMULA
|
For n < 19, a(n) = n^2 - 2n + 2. For large n, l(n) <= a(n) < n^2 - 2n + 2 + l(n), where l(n) is Landau's function (A000793). It seems the exact value is still unknown.
|
|
|
EXAMPLE
|
a(4) = 10: the matrix [[0,0,0,1], [0,0,1,0], [1,0,0,0], [0,1,1,0]] generates a semigroup of order 10 under Boolean matrix multiplication.
|
|
|
CROSSREFS
|
Cf. A000793, A202140.
Sequence in context: A303372 A159547 A002522 * A322008 A300164 A248193
Adjacent sequences: A217987 A217988 A217989 * A217991 A217992 A217993
|
|
|
KEYWORD
|
nonn,hard,more
|
|
|
AUTHOR
|
Jeffrey Shallit, Oct 17 2012
|
|
|
STATUS
|
approved
|
| |
|
|
