4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$). enter image description here

(source: Wikipedia, by Eviatar Bach)

$\endgroup$
  • $\begingroup$ Perfect---Thanks! $\endgroup$ – Joseph O'Rourke Apr 15 '17 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.