> 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.
Edit: Here's another estimate: with 6 million digits, we can get all 6 digit possibilities by just concatenating them all together. There's then (10^6)! ways to arrange the 6 digit strings before concatenating them. So if we picked a random 6 million digit sequence, there's (10^6)!/10^(6e6) ~ 10^(-10^5.6) chance of getting one of those. So the chance that a random 6 million digit string contains all subsequences is at least that high. But that's not saying very much!
This is related to the question: how many balls do I need to thrown randomly into N buckets so that the each bucket gets at least one ball (with high probability)? I was amused to learn recently that the answer must be more than linear in N. You might think that throwing a billion times N balls would suffice, but for very large N it won't. Even though you're throwing a billion times more balls than there are buckets! The probabalists I was talking to about this didn't know off-hand what the exact asymptotic of "enough balls" to throw was. That answer appears to depend upon the asymptotics of the second Stirling number based off this stack exchange [2]. But to complicate matters, the approximation given by the Wikipedia page [3] is precisely insufficient to answer the question! We'd need to know how it approaches that asymptotic.
[1] https://en.wikipedia.org/wiki/De_Bruijn_sequence [2] http://math.stackexchange.com/questions/174674/if-n-balls-ar... [3] https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second...