login
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

%I #67 Jul 01 2023 14:34:31

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

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

%U 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

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

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

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

%H Davis Smith, <a href="/A351289/b351289.txt">Table of n, a(n) for n = 2..5051; the first 100 antidiagonals of this array</a>

%H Theodoros P. Gevezes and Leonidas S. Pitsoulis, <a href="https://doi.org/10.1007/978-1-4939-0808-0_10">The Shortest Superstring Problem</a>, Optimization in Science and Engineering, Springer, 2014, 189-227.

%H Matthias Englert, Nicolaos Matsakis, and Pavel VeselĂ˝, <a href="https://arxiv.org/abs/2111.03968">Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios</a>, arXiv:2111.03968 [cs.DS], 2021.

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

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

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

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

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

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

%e The square array begins:

%e n\k| 1 2 3 4 5 6 7 8 9 10 ...

%e ===+==========================================

%e 2 | 1 2 2 3 3 6 6 4 4 4 ...

%e 3 | 1 2 5 3 3 11 11 4 4 14 ...

%e 4 | 1 2 6 3 7 11 27 4 4 18 ...

%e 5 | 1 2 7 3 8 13 38 4 9 14 ...

%e 6 | 1 2 8 3 9 15 51 4 10 16 ...

%e 7 | 1 2 9 3 10 17 66 4 11 18 ...

%e 8 | 1 2 10 3 11 19 83 4 12 20 ...

%e 9 | 1 2 11 3 12 21 102 4 13 22 ...

%e 10 | 1 2 12 3 13 23 123 4 14 24 ...

%e 11 | 1 2 13 3 14 25 146 4 15 26 ...

%e ..

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

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

%K nonn,tabl

%O 2,2

%A _Davis Smith_, Feb 06 2022