What is the shortest digit sequence containing all 4 digits sequences?

Question

Let's consider all 4 digits sequences:

0000
0001
0002
...
9999

Obviously there is a large sequence containing all of them as substrings (the concatenation of all of them).

My question is, what is the length of the smallest possible such sequence (since the minimum is attained)?

For 1 digit, the answer is clearly :

0123456789

(or any permutation).

For 2 digits numbers, it it can be shortened, since "001" contains both "00" and "01".

But I have no clue on how to get to a definitive answer.

I spotted this similar question, but I'm not interested in the permutations of the alphabet, but 4-sequences.

Answer 1

This is very closed to De Bruijn sequences.

---

Let's call $A$ your alphabet (for decimal numbers $A=\{0,\ldots,9\}$) and $n$ the length of the contained sequences. We look for sequences containing all elements as (possibly) cyclic substring.

Consider the digraph $G = (V,E)$, where:

$$V=A^{n-1}$$ $$E=\{((u_1, \ldots, u_{n-1}), (u_2, \ldots, u_{n-1}, v)), (u_1,\ldots, u_{n-1},v \in A^n\}$$

Then sequences containing all elements of $A^n$ as substring are exactly walks in $G$ going through every edge.

Each node has an in and out degree of $|A|$, so this graph has an Eulerian cycle, which leads to a sequence of length $|A|^n$ minimal possible.

---

If we delete the cycle, the same graph still works. However, the minimal length we get is now the cost of writing the $n-1$ first letters plus the $|E|$ edges, i.e. $n-1+|A|^n$. For $n=4$, $A=\{0,\ldots,9\}$, we get $10003$.