earliest string to reprsent 00 ... 99

[Max Alekseyev]

Neil, SeqFans,

I think, Patrick supposed to include 2-digit substring 00 as well (at
least the beginning of his sequence says so).

It is easy to prove that such a string exists and, moreover, it can be
closed into a circle of length 100.

Namely, let us construct a (directed) de Bruijn graph G on vertices
V={0,1,2,3,4,5,6,7,8,9}, where every vertex is connected with every
other vertex (including itself  - so, there is a self-loop at every
vertex) by a directed arc. The arcs in G "encode" all possible 2-digit
strings.

Any string over the alphabet V can be viewed as a path in G. If the
string contains all 2-digit strings as substrings, then the
corresponding path passes through every arc in G. The shortest such
path is an Eulerian one (if it exists) and it indeed exists in G.

The indegree of every vertex in G equals its outdegree, implying that
there exists an Eulerian cycle. Such a cycle has length 100 and visit
every vertex 10 times.

In this new sequence we basically want to find an Eulerian cycle
resulting in the lexicographically smallest string. I think such a
cycle can be easily found by traversing G in a greedy manner...

Regards,
Max

On Feb 13, 2008 7:44 PM, N. J. A. Sloane <njas at research.att.com> wrote:
>
> Dear Seqfans, Patrick A. Kirol submitted a sequence
> which I did not understand.  After reading his reply,
> I think that the problem can be stated as follows:
>
> Find the shortest (and lexicographically earliest)
> decimal string which contains all the 2-digit strings 01, 02,
> ..., 98, 99.
>
> Presumably something like this will be optimal:
>
> 1 0 1 1 2 1 3 ... 9 9
>
> Here is what he sent me:
>
> %S A000001 0,01,02,03,04,05,06,07,08,09,1,12,13,14,15,16,17,18,19,2,23,24,25,26,27,28,29,3,34,35,36,37,38,39,4,45,46,47,48,49,5,56,57,58,59,6,67,68,69,7,78,79,8,89,9
>
> but I think the version in the
> OEIS should be a string of single digits seperated by commas.
> The string /could/ begin with 0, but it's not obvious that that
> is optimal.
>
> Neil
>
>



I can't use the two-digit version
because the OEIS doesn't like leading zeros

the single-digit version seems to be identical
to the single-digit version of what Patrick
originally sent me, so it looks like
he had it right from the beginning

Neil
.