> Naively, you'd need at least 1 million [digits] to get all 6 digit numbers in it.
How naive do you do it? :)
When I just concatenate all possible 6-digit numbers (of which there are 1e6 = 1 million), I get 6 million digits total. You could of course overlap them partially to save space, but that does not count as "naive" anymore.
Your 6 million digits isn't a lower bound though: it's just demonstrating that 6 million digits can suffice, but there could be shorter ways to do it. In particular, none of your million 6 digit strings are overlapping. My estimate was the following. If you take a million digit string, then there are 1 million six digit substrings (actually you need 1 million and 5 digits * ). I.e. a 6 digit substring is specified by choosing where it starts, and there are 1 million places to do that. So if each of these were distinct, you'd get it. But any shorter string just doesn't have enough substrings in it to possibly get them all!
But it's not clear that it's possible to overlap all possible substrings in the right way: that's what De Bruijn sequences do but I don't consider them to be naively obvious at all.
* This is where I overlooked in my last post that De Bruijn sequences (which achieve this lower estimate) are actually for cyclic strings, allowing the subtrings to go past the end and back to the start of million digits. That allows 1 million digits to suffice. We'd actually need that 1000005 digits.
How naive do you do it? :)
When I just concatenate all possible 6-digit numbers (of which there are 1e6 = 1 million), I get 6 million digits total. You could of course overlap them partially to save space, but that does not count as "naive" anymore.