OFFSET
2,2
COMMENTS
A(n,k) is the least m such that m contains the base-n expansions of the active bits (plus 1) in k as substrings.
The Shortest Superstring Problem is, given a set of strings, S, to find the shortest string which contains each element of S as a substring. All possible solutions to this problem are contained in this array. The values of k represent the set of strings (where the active bits represent the strings in base n). The value of k for non-numeral strings (or numeral strings with an initial 0) is generated by mapping each character to a unique value 1 through n, converting from base n+1, subtracting 1 from each, raising 2 to the power of each and then summing the result. A(n+1,k) in base n+1 is the shortest superstring. The value of k for numeral strings in base n (without initial 0's) is generated by just raising 2 to the power of the value of each and then summing the result. A(n,k) in base n is the shortest superstring.
LINKS
Theodoros P. Gevezes and Leonidas S. Pitsoulis, The Shortest Superstring Problem, Optimization in Science and Engineering, Springer, 2014, 189-227.
Matthias Englert, Nicolaos Matsakis, and Pavel Veselý, Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios, arXiv:2111.03968 [cs.DS], 2021.
FORMULA
EXAMPLE
The binary expansion of 7 is 111. This means that the base-n expansions of the 7th column will contain the base-n expansions of 1, 2, and 3 as substrings. So A(6,7) = 123_6 (as that is the arrangement of those digits with the lowest value) and 123_6 = 51_10.
For another example, the binary expansion of 10 is 1010, so the 10th column will contain the base-n expansions of 2 and 4 as substrings. So A(7,10) = 24_7 (as that's the arrangement with the lowest value) and 24_7 = 18_10. Also, frequently, two or more of the substrings will overlap. For example, A(2,7) = 110_2 = 6 as the final digit of 11_2 is the same as the first digit of 10_2 and 1 is a substring of both of those.
The square array begins:
n\k| 1 2 3 4 5 6 7 8 9 10 ...
===+==========================================
2 | 1 2 2 3 3 6 6 4 4 4 ...
3 | 1 2 5 3 3 11 11 4 4 14 ...
4 | 1 2 6 3 7 11 27 4 4 18 ...
5 | 1 2 7 3 8 13 38 4 9 14 ...
6 | 1 2 8 3 9 15 51 4 10 16 ...
7 | 1 2 9 3 10 17 66 4 11 18 ...
8 | 1 2 10 3 11 19 83 4 12 20 ...
9 | 1 2 11 3 12 21 102 4 13 22 ...
10 | 1 2 12 3 13 23 123 4 14 24 ...
11 | 1 2 13 3 14 25 146 4 15 26 ...
..
PROG
(PARI) A351289(n, k)=if(hammingweight(k)==1, return(logint(k, 2)+1), my(OverSumBase(X)=fold((x, y)->my(B1=digits(x, n), B2=digits(y, n), b=select(z->B1[#B1-(z-1)..#B1]==B2[1..z], [1..min(#B1, #B2)])); fromdigits(concat(B1, B2[if(#b, vecmax(b)+1, 1)..#B2]), n), Vec(X)), K=select(z->bittest(k, z-1), [1..logint(k, 2)+1]), V=apply(x->my(X=if(x, digits(x, n), [0])); setbinop((y, z)->fromdigits(X[y..z], n), [1..#X]), K), W=select(X->my(L=List(V)); listpop(L, setsearch(K, X)); !setsearch(Set(concat(L)), X), K), P1); if(#W==1, return(W[1]), vecmax(K)<n, return(fromdigits(Set(K), n)), forperm(W, p, my(P=OverSumBase(p)); if(P1, if(P1>P, P1=P), P1=P)); print(P1); return(P1)))
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Davis Smith, Feb 06 2022
STATUS
approved