login
The OEIS is supported by the many generous donors 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. 1

%I #22 Nov 07 2023 03:16:02

%S 1,2,5,10,17,26,37,50,65,82,101,122,145,170,197,226,257,290,420

%N Size of largest semigroup generated by one Boolean n X n matrix.

%D J. Denes, K. H. Kim, and F. W. Roush, Automata on one symbol, in Studies in Pure Mathematics: To the Memory of Paul Turan, Birkhäuser, 1983, pp. 127-134.

%H George Markowsky, <a href="https://eudml.org/doc/134218">Bounds on the index and period of a binary relation on a finite set</a>, Semigroup Forum 13 (1977), 253-259.

%F 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.

%e 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.

%Y Cf. A000793, A202140.

%K nonn,hard,more

%O 1,2

%A _Jeffrey Shallit_, Oct 17 2012

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)