login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A217990 Size of largest semigroup generated by one boolean n X n matrix. 0
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 * A300164 A248193 A069987

Adjacent sequences:  A217987 A217988 A217989 * A217991 A217992 A217993

KEYWORD

nonn,hard,more

AUTHOR

Jeffrey Shallit, Oct 17 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 18:55 EDT 2018. Contains 316500 sequences. (Running on oeis4.)