3
$\begingroup$

Given a number x >= 0, in base 10, how many digits does it take to form a number that has all numbers between 0 and x inclusive as substrings?

So for example, for x = 9, the answer is trivially 10, since you need every digit once. So for example

1234567890

Is a valid answer. For x=10, some slight cleverness you can also get a 10 digit answer:

1023456789

For x=19 I believe an optimal answer has 19 digits:

1101213141516171819

A trivial upper bound is:

$$1 +\sum_{i=1}^x \lceil log(i + \epsilon) \rceil$$

for any ε such that

$$0 < \epsilon < 1$$ which sums the number of digits in all numbers <= x, and which should grow roughly as x * log(x).

Is there a tighter upper bound for its growth? And is there a fast algorithm to figure out the smallest solution given an x?

$\endgroup$
3
$\begingroup$

A closely related (and solved) problem is the problem of finding de Bruijn sequences. These are sequences of length $k^n$ from an alphabet of size $k$, which contain every possible length-$n$ string as a cyclic substring (allowing a substring that starts near the end and ends near the beginning). These are known to always exist, and the Wikipedia article has some algorithms including an implementation in Python. They're optimal for what they do, since a length-$\ell$ string has $\ell$ cyclic substrings, so to have $k^n$ distinct ones it needs length $k^n$.

From these, we get a construction for your problem. If $x$ is an $n$-digit number, then take a de Bruijn sequence of length $10^n$ which has all $n$-digit strings as cyclic substrings. (Make sure to start at a nonzero digit to make this an actual integer.) Then append the first $n-1$ digits to the end, to get a sequence of length $10^n + n - 1$ which has all $n$-digit strings as ordinary substrings.

The resulting solution is a number with at most $10x + \log_{10}x$ digits. (This happens in the worst case where $x = 10^{n-1}$, is the smallest $n$-digit number.) Asymptotically, this is best possible: when $x$ is an $n$-digit number, there are $O(x)$ distinct $(n-1)$-digit numbers smaller than $x$, so the solution must have $O(x)$ different substrings, which means it must have $O(x)$ digits.

$\endgroup$
  • $\begingroup$ Very cool, thanks! $\endgroup$ – sol_var Feb 17 at 19:59

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.