what is the minimum number containing all n-digit substrings?

Primes, divisors, arithmetic, number properties, ...
Post Reply
boomminecraft8
Posts: 1
Joined: Fri Aug 04, 2017 3:02 pm

what is the minimum number containing all n-digit substrings?

Post by boomminecraft8 » Sun Aug 13, 2017 10:17 am

Spoiler: Bad English Ahead!! 8-)

(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)

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: what is the minimum number containing all n-digit substrings?

Post by jaap » Sun Aug 13, 2017 9:44 pm

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.

Post Reply