|
| |
|
|
A351289
|
|
Square array read by descending antidiagonals: A(n,k) is the smallest m such that the base-n expansion of m contains the base-n expansions of the k-th row of A048793 as substrings.
|
|
1
|
|
|
|
1, 2, 1, 2, 2, 1, 3, 5, 2, 1, 3, 3, 6, 2, 1, 6, 3, 3, 7, 2, 1, 6, 11, 7, 3, 8, 2, 1, 4, 11, 11, 8, 3, 9, 2, 1, 4, 4, 27, 13, 9, 3, 10, 2, 1, 4, 4, 4, 38, 15, 10, 3, 11, 2, 1, 4, 14, 4, 4, 51, 17, 11, 3, 12, 2, 1, 12, 14, 18, 9, 4, 66, 19, 12, 3, 13, 2, 1, 12, 12, 18, 14, 10, 4, 83, 21, 13, 3, 14, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
A(n,2^k) = k + 1.
|
|
|
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
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
