Number substrings

Given a target integer, what's the fewest digits needed for an integer in a given base to contain all integers from 0 to the target as substring?

Here's an interesting question: given a target integer $n$ , what's the smallest number of (significant) digits an integer must have in a given base so that it contains as substrings all integers from $0$ to $n$ ?

Let's clarify with some examples, and assume for simplicity that we're working in base 10.

Obviously, for $n < 10$ , the minimum number of digits to have all numbers from $0$ to $n$ is $n + 1$ , since all numbers from $0$ to $n$ are (distinct) single-digit numbers, so, for example, for $n = 9$ you need a $10$ -digit number at least ( $9876543210$ would do, but so would $1023456789$ ; the actual number doesn't matter, we only care about the number of digits).

With two-digit numbers, things become more interesting. For example, the same $9876543210$ also has $10$ as a substring, so it works for $n = 10$ too. It doesn't work for $n = 11$ though —and for that you can prove that you need at least an $11$ -digit number because you need a repeated digit (for example, $98765432110$ ). With $n = 12$ you want to have substrings $10, 11, 12$ , and while the $11$ can share its final digit with either the $10$ or the $12$ , it can't do both, so it will need to be something like $987654312110$ , a 12-digit number.

The same argument can be repeated up to $n = 19$ ( $1918171615141312110$ ), a 19-digit number, and even for $n = 20$ you'll need to at least add a $0$ after the existing 2 ( $19181716151413120110$ ) since you can't share the 0 used for $0$ and $10$ … which is a pity, because this splits the $2$ from the $1$ that could be otherwise be used for $n = 21$ , so we need an extra digit ( $191817161514131202110$ ). Similarly, we can't easily recycle the two $2$ s we have to get to $n = 22$ (we need $20$ , $21$ and $22$ ), so we'll need another digit ( $1918171615141312022110$ , a 22-digit number), but then for $n = 23$ we can't just add one digit, because we need both another 2 and another 3: $n = 23$ needs a 24-digit number, and the same “+2” growth is needed for all numbers up to $n = 29$ , leading to the monstrous 36-digit number $191817161514131202211023242526272829$ .

Things then slow down again: for $n = 30$ we just need to add a single digit, $1918171615141312022110230242526272829$ , and this same number works for $n = 31$ , but not for $n = 32$ because we split the 3 from the 2 again …

How does the pattern flow then as $n$ grows larger? On the one hand, there should be more opportunities to use digits for multiple purposes: on the other, you need more combinations.

Is there some kind of law that can describe the pattern? Are there more opportunities to find numbers with less digits if they are rebuilt from scratch for the target $n$ , or if they are built with small changes from the previous one(s)?

UPDATE #1: a discussion thread on the Fediverse with @mau@frenfiverse.net mentions that the number of digits needed is monotonic non-decreasing. This is obvious, but just in case here's a short proof.

Let $σ_{b}$ be the function that maps the target number $n$ to the minimum number of digits needed in bases $b$ . This means that if $k = σ_{b} (n)$ then there is an integer with $k$ (significant) digits in base $b$ that includes as substrings all integers from $0$ to $n$ . Let's call such a number a $k$ -digit representative of the target $n$ in base $b$ . (Note that as exemplified in the beginning, there may be multiple representatives.)

Now consider $k_{1} = σ_{b} (n + 1)$ . If must be $k_{1} \geq k$ because by definition of $σ$ there is an integer with $k_{1}$ significant digits in base $b$ that includes as substrings all integers from $0$ to $n + 1$ , which includes all integers from $0$ to $n$ : if $k_{1}$ was strictly less than $k$ , we could use the $k_{1}$ -digit representative of $n + 1$ also for $n$ .

@mau also provides an example sequence of representatives in base 2, but I think it can be improved a little. Remember that the integers in base 2 go: 0, 1, 10, 11, 100, 101, 110, 111, 1000, … and a sequence of representatives could be: 0, 10, 10, 110, 1100, 101100 (@mau proposes 110100) 101100 (ditto), 1011100, 10111000, …

It doesn't look like OEIS has anything like this, so it might be really worth exploring this better.

The one thing that seems to emerge at least with small numbers and bases 2 and 10 is that $σ (n) \geq n$ . Does this hold for larger targets? Does it all in all bases? (I'm particularly curious about the latter for odd balanced bases.)

And for those that enjoy pure math the most when it doesn't seem to have any applications, I strongly doubt somebody will ever find a practical application to this, other than in the game I play with my kids to avoid car boredom.

UPDATE #2: new discussion thread on the Fediverse. @wqferr@mathstodon.xyz points out that this problem may be related to (generalized) superpermutations, especially when $b = 2$ , and @mrdk@mathstodon.xyz relates it to de Bruijn sequences. There are are still some significant differences in the rules that the representative should follow that have a significant impact on the number of digits, but we seem to be getting somewhere.