# Shortest universal bit string: One string to contain all others

Let $s$ be a string of bits. Treat it as a cycle, with the first bit following the last. Say that $s$ is universal for $n$ if all the $2^n$ strings of $n$ bits can be found in $s$ as consecutive, left-to-right bits (with wrap-around). Define $u(n)$ as the length of the shortest string universal for $n$.

Examples:

$u(1)=2$: $$\begin{matrix} \color{red}{0} & 1 \\ 0 & \color{red}{1} \end{matrix}$$

$u(2)=4$: $$\begin{matrix} \color{red}{0} & \color{red}{0} & 1 & 1 \\ 0 & \color{red}{0} & \color{red}{1} & 1 \\ \color{red}{0} & 0 & 1 & \color{red}{1} \\ 0 & 0 & \color{red}{1} & \color{red}{1} \end{matrix}$$

$u(3)=8$:

$$\begin{matrix} \color{red}{0} & \color{red}{0} & \color{red}{0} & 1 & 1 & 1 & 0 & 1\\ 0 & \color{red}{0} & \color{red}{0} & \color{red}{1} & 1 & 1 & 0 & 1\\ \color{red}{0} & 0 & 0 & 1 & 1 & 1 & \color{red}{0} & \color{red}{1}\\ 0 & 0 & \color{red}{0} & \color{red}{1} & \color{red}{1} & 1 & 0 & 1\\ \color{red}{0} & \color{red}{0} & 0 & 1 & 1 & 1 & 0 & \color{red}{1}\\ 0 & 0 & 0 & 1 & 1 & \color{red}{1} & \color{red}{0} & \color{red}{1}\\ 0 & 0 & 0 & 1 & \color{red}{1} & \color{red}{1} & \color{red}{0} & 1\\ 0 & 0 & 0 & \color{red}{1} & \color{red}{1} & \color{red}{1} & 0 & 1 \end{matrix}$$

Q1. What is $u(n)$?

This may be simple, but the wrap-around seems to make it not so straightforward.

Q2. What is the generalization to strings of $k$ symbols? Let $u(k,n)$ be the length of the shortest string on $k$ symbols that contains all strings of length $n$.

Likely this is all known...

What you're looking for is related to De Bruijn sequences. The formula seems to be very simple: $u(k,n) = k^n$ (and the special case $u(n) = 2^n$).