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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A157656 Maximal possible number of states in a minimal deterministic automaton, equivalent to an n-state nondeterministic automaton over 1-symbol alphabet. 0
2, 3, 6, 11, 18, 27 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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).

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".

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).

Conjecture: a(n)=A059100(n-1) holds only for all n<20 as well as n=22 and n=23. (Rustem Aidagulov)

LINKS

Table of n, a(n) for n=1..6.

Author?, Discussion of the problem (in Russian)

CROSSREFS

Sequence in context: A049794 A034031 A121617 * A059100 A131512 A147388

Adjacent sequences:  A157653 A157654 A157655 * A157657 A157658 A157659

KEYWORD

nonn,hard,more

AUTHOR

Max Alekseyev, Mar 03 2009

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 04:04 EDT 2018. Contains 316431 sequences. (Running on oeis4.)