If I understand the question correctly, brute-force search with some Julia code gives following small values \begin{array}{rr|rrrrrrrrrrrrrrrrr} && n\\ && 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline m & 2 & 4 & = \\ & 3 & & 7 & 8 & = \\ & 4 & & & 11 & 13 & 14 & 15 & 16 & = \\ & 5 & & & & 16 & 19 & 21 & 23 & 25 & 27 & 30 & 31 & 32 & = \\ & 6 & & & & & 22 & 26 & 29 & 32 & 35 & 38 & 41 & 45 & 48 \\ & 7 & & & & & & 29 & 34 & 38 & 42 & 46 & 50 & 54 & 58 \\ & 8 & & & & & & & 37 & 43 & 48 & 53 & 58 & 63 & 68 \\ & 9 & & & & & & & & 46 & 53 & 59 & 65 & 71 & 77 \\ & 10& & & & & & & & & 56 & 64 & 71 & 78 & 85 \\ & 11& & & & & & & & & & 67 & 76 & 84 & 92 \\ & 12& & & & & & & & & & & 79 & 89 & 98 \\ & 13& & & & & & & & & & & & 92 & 103 \\ & 14& & & & & & & & & & & & & 106 \\ \end{array} "=" means that the rest of the row repeats the last value, that is, there is a string that exhibits all $2^m$ subsets (adding more length will not change this). Looking at diagonals: * The main diagonal is as described in the question. * The first superdiagonal 4,8,13,19,26,34,43,53,64,76 has [one OEIS match][1], A034856 "a(n) = binomial(n+1, 2) + n - 1 = n*(n + 3)/2 - 1". * The second superdiagonal has no OEIS entry but OEIS [guesses][2] it to be a quadratic. Same with third superdiagonal. * The fourth superdiagonal, starting from 16,25,35,46,58,71,85,100,116,133,151 has [two matches][3] (but different values before the 16). If we write $T(m)$ for the smallest $n$ where $2^m$ appears, $T$ forms a sequence that starts 1,2,4,8,13, which matches many things in OEIS. Examples of shortest strings where all $2^m$ subsets of alphabet $\{1,2,\ldots,m\}$ appear are: \begin{array}{l|l} m & T(m) \\ \hline 1 & 1 & 1 \\ 2 & 2 & 12 \\ 3 & 4 & 1231 \\ 4 & 8 & 12314234 \\ 5 & 13 & 1234512413524 \\ \end{array} [1]: https://oeis.org/search?q=4%2C8%2C13%2C19%2C26%2C34%2C43%2C53%2C64%2C76&sort=&language=&go=Search [2]: https://oeis.org/search?q=8%2C14%2C21%2C29%2C38%2C48%2C59%2C71%2C84&sort=&language=&go=Search [3]: https://oeis.org/search?q=16%2C25%2C35%2C46%2C58%2C71%2C85%2C100%2C116%2C133%2C151&sort=&language=&go=Search