automatons over 1-symbol alphabet

[Max]

Hello!

I would like to bring to your attention the following sequence.

Let a(n) be the maximum number of states of the minimum deterministic automaton that is equivalent to a nondeterministic automaton with n states over 1-symbol alphabet.

Alternative definition:

Suppose that we have a labyrinth consisting of n rooms and one-way corridors connecting some of them (two rooms A and B may be connected by two corridors A->B and B->A). One room is called starting.
Let R(k) be a set of all rooms that can be reached from the starting room after passing through exactly k corridors. We need to construct a labyrinth with the maximum 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).

This problem was proposed by Sergey Podzorov in russian math forum http://www.nsu.ru/phorum/read.php?f=29&i=5505&t=5505

By direct enumeration I've shown that a(n)=(n-1)^2+2 for n=1..6. A labyrinth giving rise to this number looks like

v----------|
1->2->...->n
...^_______|

where 1,2,...,n are rooms with the starting room 1 and the arrows are corridors.

For example, for n=3 this labyrinth gives
R(0) = { 1 }
R(1) = { 2 }
R(2) = { 3 }
R(3) = { 1, 2 }
R(4) = { 2, 3 }
R(5) = { 1, 2, 3 }
R(6) = { 1, 2, 3 }
...
implying a(3)=6.


Rustem Aidagulov claims that the formula a(n)=(n-1)^2+2 holds for all n<20, n=22, and n=23 but nobody has verified his claim yet.

For larger n, the number (n-1)^2+2 is not the best possible.
For example, for n=29 there is a labyrinth of the following shape. There are five directed corridors from the starting room to five other rooms that belong to disjoint directed cycles of length 2,3,5,7,11 respectively. This labyrinth gives 1+2*3*5*7*11=2311 distinct R(k)'s and 2311>=(29-1)^2+2=786.

It makes sense to add the sequence a(n) to OEIS but all known values coincide with the sequence (n-1)^2+2=A059100(n-1).
What should we do in this case?

Your help in extending and/or analyzing this sequence will be appreciated.

Max