cp's OEIS Frontend

A157656 Maximal possible number of states in a minimal deterministic automaton, equivalent to an n-state nondeterministic automaton over 1-symbol alphabet.

%I A157656 #13 Dec 16 2023 00:04:47
%S A157656 2,3,6,11,18,27
%N A157656 Maximal possible number of states in a minimal deterministic automaton, equivalent to an n-state nondeterministic automaton over 1-symbol alphabet.
%C A157656 Alternative definition: consider a labyrinth consisting of n rooms, one designated as the "start room", connected by a number of one-way corridors. Let R(k) be a set of all rooms that can be reached from the start room after passing through exactly k corridors. We need to construct a labyrinth with the maximal number of distinct R(k), i.e., a set { R(0), R(1), R(2), ... } (that is actually a finite set) must be of the largest possible size. This size is a(n).
%C A157656 For small n, a(n)=A059100(n-1) which corresponds to a labyrinth 1 -> 2 -> 3 -> ... -> n -> 1, n -> 2 with the start room "1".
%C A157656 For large n, a(n) is different from A059100(n-1). In particular, for n=29, there is a labyrinth of the following shape: there are five directed corridors from the start room to five other rooms that belong to disjoint directed cycles of length 2, 3, 5, 7, and 11 respectively (note that 29 = 1+2+3+5+7+11). It gives 1+2*3*5*7*11=2311 distinct R(k)'s, implying that a(29)>=2311>A059100(28).
%C A157656 Conjecture: a(n)=A059100(n-1) holds only for all n<20 as well as n=22 and n=23. (Rustem Aidagulov)
%C A157656 In general, a(n) >= A000793(n-1)+1. The strategy is to partition n-1 into coprime numbers with maximum product and create a cycle for each, then add one more starting node which is connected to all cycles. This also implies that a(n) is Omega(e^sqrt(n log n)). - _Martín Muñoz_, Dec 10 2023
%H A157656 Author?, <a href="http://www.nsu.ru/phorum/read.php?f=29&amp;i=5505&amp;t=5505">Discussion of the problem</a> (in Russian)
%Y A157656 Cf. A059100, A000793.
%K A157656 nonn,hard,more
%O A157656 1,1
%A A157656 _Max Alekseyev_, Mar 03 2009