What are the odds that this worked? Or, how many digits should we expect to need? Naively, you'd need at least 1 million to get all 6 digit numbers in it. If Pi

What are the odds that this worked? Or, how many digits should we expect to need? Naively, you'd need at least 1 million to get all 6 digit numbers in it. If Pi happened to be a De Bruijn sequence [1], then that would suffice. However, there are only (10!)^(10^5)/10^6 ~ 2e655970 such sequences, compared to 10^(10^6) total random sequences. I.e. the probability of getting a De Bruijn at random with a million characters is about 2e-344030. I'll round that up to "ain't gunna happen". So we probably need a lot more than the naive lower estimate... but where does it start getting likely? 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 https://en.wikipedia.org/wiki/De_Bruijn_sequence [2] http://math.stackexchange.com/questions/174674/if-n-balls-are-thrown-into-k-bins-what-is-the-probability-that-every-bin-gets-a http://math.stackexchange.com/questions/174674/if-n-balls-ar... [3] https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Asymptotic_approximation https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second...