Spoiler: Bad English Ahead!!
(1a) The question I want to ask is in the topic. I am trying to find if there is some generalized way to find the minimum number that "contain" all n-digit (or below) number, as "substrings".
(1b) If there isn't, is there anyway to find out the number of digits of the number?
i.e. for n = 1, I am trying to find the number that contains all the 1-digit number i.e. "0 ~ 9" (0 is 1-digit)
which turns out to be
1023456789, with 10 digits.
As a little "Extension" to (1b), can all the subsequence substrings with "length 2" for the "n=2" case contain all 2-digit number without repeat?
for example: suppose the answer be "1295837152"
All the substrings in the answer are:
12,29,95,58,83,37,71,15,52
which do not repeat.
And in general, how about for "n = k"? (k is positive integers)
(n=1 is True, since the substrings in 1023456789 are just the 1-digit numbers, which would be distinct)
what is the minimum number containing all n-digit substrings?
-
- Posts: 1
- Joined: Fri Aug 04, 2017 4:02 pm
Re: what is the minimum number containing all n-digit substrings?
These are called De Bruijn sequences.
It is always possible if you start with all $k$-digit decimal strings (there are $10^k$ of them as leading zeros are allowed), to string them together with maximal overlap to create an optimal sequence that is $10^k+k-1$ long. The last $k-1$ digits will be the same as the first, so it can be considered a cycle of $10^k$ digits, where all $10^k$ possible length $k$ substrings occur exactly once.
It is always possible if you start with all $k$-digit decimal strings (there are $10^k$ of them as leading zeros are allowed), to string them together with maximal overlap to create an optimal sequence that is $10^k+k-1$ long. The last $k-1$ digits will be the same as the first, so it can be considered a cycle of $10^k$ digits, where all $10^k$ possible length $k$ substrings occur exactly once.