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, 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

Offset: 2

Author

Davis Smith, Feb 06 2022

Keywords

• nonn
• tabl

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.

Examples

			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 ...
  ..
		

Links

• Davis Smith, Table of n, a(n) for n = 2..5051; the first 100 antidiagonals of this array
• 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.

Crossrefs

Cf. A000120, A048793, A056744, A070939, A133457, A350510.

Programs

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)P,P1=P),P1=P));print(P1);return(P1)))

Formula

A(n,2^k) = k + 1.

A(n,2^k - 1) = A350510(n,k).

A(2,2^k - 1) = A056744(k).

For n > A070939(k), A(n,k) = Sum_{i=1..A000120(k)} A048793(k,i)*n^(A000120(k) - i).